Ćwiczenia/1. Ćwiczenia/Zadanie 2 (sortowanie listy jednokierunkowej).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Proszę zaimplementować algorytm sortowania listy jednokierunkowej. W szczególności należy:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Zdefiniować klasę w Pythonie realizującą listę jednokierunkową."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. Zaimplementować wstawianie do posortowanej listy."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. Zaimplementować usuwanie maksimum z listy."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4. Zaimplementować sortowanie przez wstawianie lub sortowanie przez wybieranie na podstawie powyższych funkcji"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### #1 Deklaracja klasy, reprezentującej listę jednokierunkową"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.next = None\n",
    "        self.val = val\n",
    "        \n",
    "        \n",
    "class LinkedList:\n",
    "    def __init__(self, values=None):\n",
    "        self.head = self.tail = None\n",
    "        self.length = 0\n",
    "        values and self.extend(values)\n",
    "        \n",
    "    def __len__(self):\n",
    "        return self.length\n",
    "    \n",
    "    def __iter__(self):\n",
    "        curr = self.head\n",
    "        while curr:\n",
    "            yield curr.val\n",
    "            curr = curr.next\n",
    "    \n",
    "    def __str__(self):\n",
    "        return ' -> '.join(str(v) for v in self)\n",
    "        \n",
    "    def append(self, val):\n",
    "        node = Node(val)\n",
    "        if not self:\n",
    "            self.head = self.tail = node\n",
    "        else:\n",
    "            self.tail.next = node\n",
    "            self.tail = node\n",
    "        self.length += 1\n",
    "        \n",
    "    def prepend(self, val):\n",
    "        node = Node(val)\n",
    "        if not self:\n",
    "            self.head = self.tail = node\n",
    "        else:\n",
    "            node.next = self.head\n",
    "            self.head = node\n",
    "        self.length += 1\n",
    "        \n",
    "    def extend(self, values):\n",
    "        for val in values:\n",
    "            self.append(val)\n",
    "            \n",
    "    def popleft(self):\n",
    "        if not self:\n",
    "            raise IndexError(f'pop from an empty {self.__class__.__name__}')\n",
    "        removed = self.head.val\n",
    "        self.head = self.head.next\n",
    "        self.length -= 1\n",
    "        return removed\n",
    "            \n",
    "    def insert_after(self, val, node):\n",
    "        new_node = Node(val)\n",
    "        new_node.next = node.next\n",
    "        node.next = new_node\n",
    "        self.length += 1\n",
    "        \n",
    "    def remove_next_node(self, node):\n",
    "        if node is not self.tail:\n",
    "            removed = node.next\n",
    "            if removed is self.tail:\n",
    "                self.tail = node\n",
    "            node.next = removed.next\n",
    "            self.length -= 1\n",
    "            return removed"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Przykładowy test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-68 -> -65 -> -20 -> 5 -> 44 -> 83\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "sorted_lst = sorted([random.randint(-100, 100) for _ in range(6)])\n",
    "ll = LinkedList(sorted_lst)\n",
    "\n",
    "print(ll)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### #2 Wstawianie do posortowanej listy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insert_val(ll, val):  # Linked List ll must be sorted in an increasing order\n",
    "    if not ll or val > ll.tail.val:\n",
    "        ll.append(val)\n",
    "    elif val < ll.head.val:\n",
    "        ll.prepend(val)\n",
    "    else:\n",
    "        curr = ll.head\n",
    "        while val > curr.next.val:\n",
    "            curr = curr.next\n",
    "        ll.insert_after(val, curr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Przykładowy test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-68 -> -65 -> -20 -> 5 -> 44 -> 83\n",
      "-100 -> -68 -> -65 -> -20 -> 0 -> 5 -> 44 -> 50 -> 83 -> 100\n"
     ]
    }
   ],
   "source": [
    "ll = LinkedList(sorted_lst)\n",
    "\n",
    "print(ll)\n",
    "insert_val(ll, 50)\n",
    "insert_val(ll, -100)\n",
    "insert_val(ll, 100)\n",
    "insert_val(ll, 0)\n",
    "print(ll)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### #3 Usuwanie maksimum z listy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def remove_max(ll):\n",
    "    # Add a sentinel node\n",
    "    ll.prepend(None)\n",
    "    # Create pointers to previous nodes\n",
    "    max_prev = ll.head\n",
    "    curr_prev = ll.head.next\n",
    "    # Loop till the current node exists\n",
    "    while curr_prev.next:\n",
    "        if curr_prev.next.val > max_prev.next.val:\n",
    "            max_prev = curr_prev\n",
    "        curr_prev = curr_prev.next\n",
    "        \n",
    "    # Remove a maximum value from a Linked List\n",
    "    removed = ll.remove_next_node(max_prev)\n",
    "    # Remove a sentinel node\n",
    "    ll.popleft()\n",
    "    \n",
    "    return removed.val"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Przykładowy test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Expected: 84\n",
      "-10 -> 84 -> 7 -> 29 -> 40\n",
      "Received: 84\n",
      "\n",
      "Expected: 40 \tRemoved: 40\n",
      "Expected: 29 \tRemoved: 29\n",
      "Expected: 7 \tRemoved: 7\n",
      "Expected: -10 \tRemoved: -10\n"
     ]
    }
   ],
   "source": [
    "values = [random.randint(-100, 100) for _ in range(random.randint(5, 15))]\n",
    "print('Expected:', max(values))\n",
    "ll = LinkedList(values)\n",
    "print(ll)\n",
    "max_val = remove_max(ll)\n",
    "print('Received:', max_val, end='\\n\\n')\n",
    "\n",
    "while ll:\n",
    "    print('Expected:', max(ll), '\\tRemoved:', remove_max(ll))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### #4\n",
    "#### Implementacja funkcji testującej, czy lista jest prawidłowo posortowana\n",
    "##### (to nie jest częścią zadania)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def test_sort(sort_fn, *, samples=20):\n",
    "    passed = 0\n",
    "    for i in range(samples):\n",
    "        values = [random.randint(-100, 100) for _ in range(random.randint(5, 30))]\n",
    "        expected = sorted(values)\n",
    "        ll = LinkedList(values)\n",
    "        sort_fn(ll)\n",
    "        result = list(ll)\n",
    "        passed += result == expected\n",
    "        print(f'#{i+1} Loop (passed: {passed}/{samples}):')\n",
    "        print(f'Proper answer: {expected}')\n",
    "        print(f'After sorting: {result}')\n",
    "        print()\n",
    "    print(f'Total passed tests: {passed}/{samples}')\n",
    "    print(f'A sorting algorithm is implemented {\"correctly\" if passed == samples else \"improperly\"}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### #4 a) sortowanie przez wstawianie"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insert_node(ll, node):  # Inserts node in a right position maintaining the ascending order\n",
    "    # Prepend the node\n",
    "    if node.val < ll.head.val:\n",
    "        node.next = ll.head\n",
    "        ll.head = node\n",
    "    # Insert the node before a greater one\n",
    "    else:\n",
    "        curr = ll.head\n",
    "        while node.val > curr.next.val:\n",
    "            curr = curr.next\n",
    "        node.next = curr.next\n",
    "        curr.next = node\n",
    "    ll.length += 1\n",
    "    \n",
    "def insertion_sort(ll):\n",
    "    if len(ll) < 2: return\n",
    "    \n",
    "    prev = ll.head\n",
    "    while prev.next: # We start from the second node (prev.next)\n",
    "        # If a current node (prev.next) has a value lower than a prev node, we have to\n",
    "        # shift this node to a right position before.\n",
    "        if prev.next.val < prev.val:\n",
    "            removed = ll.remove_next_node(prev)       # We removed a curr node\n",
    "            insert_node(ll, removed) # Now we insert this node in a right position\n",
    "        # We can skip a current node otherwise.\n",
    "        else:\n",
    "            prev = prev.next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Przykładowy test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#1 Loop (passed: 1/100):\n",
      "Proper answer: [-86, -84, -82, -77, -76, -73, -65, -51, -44, -40, -26, -11, 5, 9, 28, 65, 85, 89, 92, 95]\n",
      "After sorting: [-86, -84, -82, -77, -76, -73, -65, -51, -44, -40, -26, -11, 5, 9, 28, 65, 85, 89, 92, 95]\n",
      "\n",
      "#2 Loop (passed: 2/100):\n",
      "Proper answer: [-66, -41, -39, 40, 50, 72, 85]\n",
      "After sorting: [-66, -41, -39, 40, 50, 72, 85]\n",
      "\n",
      "#3 Loop (passed: 3/100):\n",
      "Proper answer: [-98, -90, -89, -85, -72, -65, -60, -48, -37, -26, -8, 0, 12, 14, 18, 19, 24, 29, 38, 50, 51, 70, 70, 75, 83, 94, 98]\n",
      "After sorting: [-98, -90, -89, -85, -72, -65, -60, -48, -37, -26, -8, 0, 12, 14, 18, 19, 24, 29, 38, 50, 51, 70, 70, 75, 83, 94, 98]\n",
      "\n",
      "#4 Loop (passed: 4/100):\n",
      "Proper answer: [-98, -47, -22, 88, 91, 94]\n",
      "After sorting: [-98, -47, -22, 88, 91, 94]\n",
      "\n",
      "#5 Loop (passed: 5/100):\n",
      "Proper answer: [-92, -70, -68, -66, -61, -60, -60, -58, -56, -46, -37, -27, -18, -14, -1, 9, 17, 19, 60, 61, 64, 65, 73, 74, 82, 91]\n",
      "After sorting: [-92, -70, -68, -66, -61, -60, -60, -58, -56, -46, -37, -27, -18, -14, -1, 9, 17, 19, 60, 61, 64, 65, 73, 74, 82, 91]\n",
      "\n",
      "#6 Loop (passed: 6/100):\n",
      "Proper answer: [-74, -69, -64, -63, -62, -53, -50, -41, -40, -27, -25, -3, 2, 8, 12, 19, 23, 31, 37, 70, 83]\n",
      "After sorting: [-74, -69, -64, -63, -62, -53, -50, -41, -40, -27, -25, -3, 2, 8, 12, 19, 23, 31, 37, 70, 83]\n",
      "\n",
      "#7 Loop (passed: 7/100):\n",
      "Proper answer: [-90, -60, -45, -18, 7, 11, 21, 37, 38, 49, 62, 72, 73, 76, 96, 97, 98]\n",
      "After sorting: [-90, -60, -45, -18, 7, 11, 21, 37, 38, 49, 62, 72, 73, 76, 96, 97, 98]\n",
      "\n",
      "#8 Loop (passed: 8/100):\n",
      "Proper answer: [-86, -84, -80, -74, -72, -71, -60, -52, -40, -29, -26, -12, -5, -3, 0, 6, 12, 19, 29, 59, 73, 93, 100]\n",
      "After sorting: [-86, -84, -80, -74, -72, -71, -60, -52, -40, -29, -26, -12, -5, -3, 0, 6, 12, 19, 29, 59, 73, 93, 100]\n",
      "\n",
      "#9 Loop (passed: 9/100):\n",
      "Proper answer: [-99, -98, -96, -93, -92, -91, -85, -65, -58, -47, -46, -42, -37, -35, -26, -11, -6, 6, 12, 37, 39, 40, 52, 74, 82]\n",
      "After sorting: [-99, -98, -96, -93, -92, -91, -85, -65, -58, -47, -46, -42, -37, -35, -26, -11, -6, 6, 12, 37, 39, 40, 52, 74, 82]\n",
      "\n",
      "#10 Loop (passed: 10/100):\n",
      "Proper answer: [-97, -79, -74, -70, -69, -58, -56, -48, -48, -47, -25, -23, -11, -3, 3, 5, 26, 33, 36, 44, 56, 58, 70, 73, 88, 91, 91, 95]\n",
      "After sorting: [-97, -79, -74, -70, -69, -58, -56, -48, -48, -47, -25, -23, -11, -3, 3, 5, 26, 33, 36, 44, 56, 58, 70, 73, 88, 91, 91, 95]\n",
      "\n",
      "#11 Loop (passed: 11/100):\n",
      "Proper answer: [-77, -71, -63, -32, -30, -2, 6, 30, 53, 71, 75, 83]\n",
      "After sorting: [-77, -71, -63, -32, -30, -2, 6, 30, 53, 71, 75, 83]\n",
      "\n",
      "#12 Loop (passed: 12/100):\n",
      "Proper answer: [-96, -73, -61, -56, -35, -9, -6, 15, 24, 72, 73, 79, 91]\n",
      "After sorting: [-96, -73, -61, -56, -35, -9, -6, 15, 24, 72, 73, 79, 91]\n",
      "\n",
      "#13 Loop (passed: 13/100):\n",
      "Proper answer: [-100, -99, -98, -96, -94, -79, -73, -66, -65, -62, -53, -52, -45, -40, -36, -36, -35, -31, -12, -12, 2, 6, 7, 15, 25, 50, 59, 66, 68, 89]\n",
      "After sorting: [-100, -99, -98, -96, -94, -79, -73, -66, -65, -62, -53, -52, -45, -40, -36, -36, -35, -31, -12, -12, 2, 6, 7, 15, 25, 50, 59, 66, 68, 89]\n",
      "\n",
      "#14 Loop (passed: 14/100):\n",
      "Proper answer: [-87, -84, -59, -42, -42, -38, -37, -24, -17, -3, 11, 19, 42, 70]\n",
      "After sorting: [-87, -84, -59, -42, -42, -38, -37, -24, -17, -3, 11, 19, 42, 70]\n",
      "\n",
      "#15 Loop (passed: 15/100):\n",
      "Proper answer: [-59, -56, -39, -9, -3, 29, 39, 58, 62, 64, 64, 66, 80]\n",
      "After sorting: [-59, -56, -39, -9, -3, 29, 39, 58, 62, 64, 64, 66, 80]\n",
      "\n",
      "#16 Loop (passed: 16/100):\n",
      "Proper answer: [-100, -74, -51, -49, -48, -46, -42, -33, -25, -1, 19, 35, 62, 78, 83, 94, 95, 97]\n",
      "After sorting: [-100, -74, -51, -49, -48, -46, -42, -33, -25, -1, 19, 35, 62, 78, 83, 94, 95, 97]\n",
      "\n",
      "#17 Loop (passed: 17/100):\n",
      "Proper answer: [-73, -69, -64, -63, -52, -49, -6, 0, 2, 17, 18, 28, 34, 45, 57, 78, 81, 89]\n",
      "After sorting: [-73, -69, -64, -63, -52, -49, -6, 0, 2, 17, 18, 28, 34, 45, 57, 78, 81, 89]\n",
      "\n",
      "#18 Loop (passed: 18/100):\n",
      "Proper answer: [-99, -80, -63, -26, -24, -21, -19, -9, -7, 6, 40, 45, 60, 61, 76, 78, 86, 86, 90, 98]\n",
      "After sorting: [-99, -80, -63, -26, -24, -21, -19, -9, -7, 6, 40, 45, 60, 61, 76, 78, 86, 86, 90, 98]\n",
      "\n",
      "#19 Loop (passed: 19/100):\n",
      "Proper answer: [-89, -69, -48, -44, -25, -8, 7, 21, 77, 80, 91, 97]\n",
      "After sorting: [-89, -69, -48, -44, -25, -8, 7, 21, 77, 80, 91, 97]\n",
      "\n",
      "#20 Loop (passed: 20/100):\n",
      "Proper answer: [-98, -86, -77, -66, -63, -61, -39, -23, -22, -17, -15, -15, -9, -8, -5, -1, 1, 9, 26, 29, 33, 47, 47, 48, 81]\n",
      "After sorting: [-98, -86, -77, -66, -63, -61, -39, -23, -22, -17, -15, -15, -9, -8, -5, -1, 1, 9, 26, 29, 33, 47, 47, 48, 81]\n",
      "\n",
      "#21 Loop (passed: 21/100):\n",
      "Proper answer: [-99, -89, -88, -87, -79, -73, -67, -55, -52, -50, -45, -29, -3, -2, 14, 20, 23, 26, 36, 41, 43, 48, 57, 62, 63, 73, 85, 89, 94, 98]\n",
      "After sorting: [-99, -89, -88, -87, -79, -73, -67, -55, -52, -50, -45, -29, -3, -2, 14, 20, 23, 26, 36, 41, 43, 48, 57, 62, 63, 73, 85, 89, 94, 98]\n",
      "\n",
      "#22 Loop (passed: 22/100):\n",
      "Proper answer: [-100, -98, -87, -86, -73, -44, -39, -23, -21, -11, 3, 5, 12, 16, 29, 34, 35, 49, 64, 96, 98]\n",
      "After sorting: [-100, -98, -87, -86, -73, -44, -39, -23, -21, -11, 3, 5, 12, 16, 29, 34, 35, 49, 64, 96, 98]\n",
      "\n",
      "#23 Loop (passed: 23/100):\n",
      "Proper answer: [-100, -70, -58, -55, -47, -37, -21, -13, -10, -5, -5, 0, 2, 11, 11, 39, 52, 56, 83]\n",
      "After sorting: [-100, -70, -58, -55, -47, -37, -21, -13, -10, -5, -5, 0, 2, 11, 11, 39, 52, 56, 83]\n",
      "\n",
      "#24 Loop (passed: 24/100):\n",
      "Proper answer: [-79, -75, -58, -58, -55, -52, -51, -47, -41, -38, -25, -19, -16, -13, -6, 6, 13, 14, 24, 26, 28, 31, 35, 42, 62, 65, 68, 89, 92]\n",
      "After sorting: [-79, -75, -58, -58, -55, -52, -51, -47, -41, -38, -25, -19, -16, -13, -6, 6, 13, 14, 24, 26, 28, 31, 35, 42, 62, 65, 68, 89, 92]\n",
      "\n",
      "#25 Loop (passed: 25/100):\n",
      "Proper answer: [-53, -48, -44, -38, -37, -21, -17, 22, 24, 56, 60, 60, 62, 63, 71, 95, 97]\n",
      "After sorting: [-53, -48, -44, -38, -37, -21, -17, 22, 24, 56, 60, 60, 62, 63, 71, 95, 97]\n",
      "\n",
      "#26 Loop (passed: 26/100):\n",
      "Proper answer: [-77, -68, -60, -57, -55, -52, -42, -36, -11, -7, -6, -6, 12, 13, 16, 21, 29, 30, 36, 37, 40, 49, 58, 68, 86, 90, 90, 96, 100]\n",
      "After sorting: [-77, -68, -60, -57, -55, -52, -42, -36, -11, -7, -6, -6, 12, 13, 16, 21, 29, 30, 36, 37, 40, 49, 58, 68, 86, 90, 90, 96, 100]\n",
      "\n",
      "#27 Loop (passed: 27/100):\n",
      "Proper answer: [-94, -92, -80, -61, -60, -41, -35, -29, -23, -22, -17, -17, -15, 12, 30, 38, 66, 80, 94, 98]\n",
      "After sorting: [-94, -92, -80, -61, -60, -41, -35, -29, -23, -22, -17, -17, -15, 12, 30, 38, 66, 80, 94, 98]\n",
      "\n",
      "#28 Loop (passed: 28/100):\n",
      "Proper answer: [-89, -76, -62, -60, -58, -50, -48, -42, -38, -30, -11, -10, 1, 18, 24, 26, 28, 38, 40, 62, 63, 63, 84, 84, 90, 91]\n",
      "After sorting: [-89, -76, -62, -60, -58, -50, -48, -42, -38, -30, -11, -10, 1, 18, 24, 26, 28, 38, 40, 62, 63, 63, 84, 84, 90, 91]\n",
      "\n",
      "#29 Loop (passed: 29/100):\n",
      "Proper answer: [-96, -92, -87, -77, -62, -54, -51, -44, -39, -34, -29, -25, -20, -19, -18, -16, -6, -6, -1, 0, 12, 25, 38, 40, 51, 58, 62, 76, 77]\n",
      "After sorting: [-96, -92, -87, -77, -62, -54, -51, -44, -39, -34, -29, -25, -20, -19, -18, -16, -6, -6, -1, 0, 12, 25, 38, 40, 51, 58, 62, 76, 77]\n",
      "\n",
      "#30 Loop (passed: 30/100):\n",
      "Proper answer: [-83, -83, -75, -62, -61, -60, -60, -59, -55, -51, -27, -15, 2, 9, 11, 15, 15, 27, 40, 45, 48, 52, 58, 65, 68, 81, 84, 84, 85, 96]\n",
      "After sorting: [-83, -83, -75, -62, -61, -60, -60, -59, -55, -51, -27, -15, 2, 9, 11, 15, 15, 27, 40, 45, 48, 52, 58, 65, 68, 81, 84, 84, 85, 96]\n",
      "\n",
      "#31 Loop (passed: 31/100):\n",
      "Proper answer: [-83, -82, -66, -22, 11, 96, 99]\n",
      "After sorting: [-83, -82, -66, -22, 11, 96, 99]\n",
      "\n",
      "#32 Loop (passed: 32/100):\n",
      "Proper answer: [-99, -91, -81, -28, 32, 38, 62, 72]\n",
      "After sorting: [-99, -91, -81, -28, 32, 38, 62, 72]\n",
      "\n",
      "#33 Loop (passed: 33/100):\n",
      "Proper answer: [-100, -87, -79, -65, -61, -31, -17, -9, 7, 26, 70, 82, 90, 96]\n",
      "After sorting: [-100, -87, -79, -65, -61, -31, -17, -9, 7, 26, 70, 82, 90, 96]\n",
      "\n",
      "#34 Loop (passed: 34/100):\n",
      "Proper answer: [-99, -91, -61, -49, -47, -45, -26, -10, -4, -1, 3, 38, 62, 82, 82, 87]\n",
      "After sorting: [-99, -91, -61, -49, -47, -45, -26, -10, -4, -1, 3, 38, 62, 82, 82, 87]\n",
      "\n",
      "#35 Loop (passed: 35/100):\n",
      "Proper answer: [-95, -83, -75, -68, -62, -45, -40, -20, -11, 10, 16, 19, 26, 31, 38, 40, 54, 84, 85, 97]\n",
      "After sorting: [-95, -83, -75, -68, -62, -45, -40, -20, -11, 10, 16, 19, 26, 31, 38, 40, 54, 84, 85, 97]\n",
      "\n",
      "#36 Loop (passed: 36/100):\n",
      "Proper answer: [-90, -24, 7, 17, 25, 39, 42, 46, 57, 62, 81]\n",
      "After sorting: [-90, -24, 7, 17, 25, 39, 42, 46, 57, 62, 81]\n",
      "\n",
      "#37 Loop (passed: 37/100):\n",
      "Proper answer: [-93, -78, -62, -56, -51, -39, -12, 6, 26, 50, 55, 67, 86, 98]\n",
      "After sorting: [-93, -78, -62, -56, -51, -39, -12, 6, 26, 50, 55, 67, 86, 98]\n",
      "\n",
      "#38 Loop (passed: 38/100):\n",
      "Proper answer: [-86, -50, -49, -46, -40, -33, -32, -27, -25, -9, 28, 34, 34, 37, 41, 59, 63, 64, 67, 71, 73, 98]\n",
      "After sorting: [-86, -50, -49, -46, -40, -33, -32, -27, -25, -9, 28, 34, 34, 37, 41, 59, 63, 64, 67, 71, 73, 98]\n",
      "\n",
      "#39 Loop (passed: 39/100):\n",
      "Proper answer: [-98, -85, -42, -24, -23, -18, -17, -1, 5, 19, 30, 43, 66, 67, 70, 98]\n",
      "After sorting: [-98, -85, -42, -24, -23, -18, -17, -1, 5, 19, 30, 43, 66, 67, 70, 98]\n",
      "\n",
      "#40 Loop (passed: 40/100):\n",
      "Proper answer: [-100, -89, -84, -83, -70, -69, -48, -33, -32, -24, 7, 14, 16, 29, 44, 44, 55, 59, 70, 78, 84, 84, 88, 96, 100]\n",
      "After sorting: [-100, -89, -84, -83, -70, -69, -48, -33, -32, -24, 7, 14, 16, 29, 44, 44, 55, 59, 70, 78, 84, 84, 88, 96, 100]\n",
      "\n",
      "#41 Loop (passed: 41/100):\n",
      "Proper answer: [-91, -39, 14, 68, 82, 90]\n",
      "After sorting: [-91, -39, 14, 68, 82, 90]\n",
      "\n",
      "#42 Loop (passed: 42/100):\n",
      "Proper answer: [-99, -99, -98, -94, -89, -81, -63, -49, -41, -40, -30, -22, -12, 5, 24, 28, 34, 37, 39, 55, 56, 73, 92, 92, 94, 97]\n",
      "After sorting: [-99, -99, -98, -94, -89, -81, -63, -49, -41, -40, -30, -22, -12, 5, 24, 28, 34, 37, 39, 55, 56, 73, 92, 92, 94, 97]\n",
      "\n",
      "#43 Loop (passed: 43/100):\n",
      "Proper answer: [-99, -96, -92, -87, -76, -47, -45, -41, -22, -7, 3, 4, 10, 15, 15, 18, 35, 44, 50, 53, 63, 67, 71, 93, 100]\n",
      "After sorting: [-99, -96, -92, -87, -76, -47, -45, -41, -22, -7, 3, 4, 10, 15, 15, 18, 35, 44, 50, 53, 63, 67, 71, 93, 100]\n",
      "\n",
      "#44 Loop (passed: 44/100):\n",
      "Proper answer: [-96, -76, -55, -45, -24, -15, -10, -10, 0, 4, 47, 56]\n",
      "After sorting: [-96, -76, -55, -45, -24, -15, -10, -10, 0, 4, 47, 56]\n",
      "\n",
      "#45 Loop (passed: 45/100):\n",
      "Proper answer: [-67, -44, -41, -34, -18, 5, 41, 87]\n",
      "After sorting: [-67, -44, -41, -34, -18, 5, 41, 87]\n",
      "\n",
      "#46 Loop (passed: 46/100):\n",
      "Proper answer: [-93, -91, -90, -65, -46, -21, -5, 0, 12, 12, 16, 17, 20, 23, 29, 42, 42, 48, 60, 71, 71, 88]\n",
      "After sorting: [-93, -91, -90, -65, -46, -21, -5, 0, 12, 12, 16, 17, 20, 23, 29, 42, 42, 48, 60, 71, 71, 88]\n",
      "\n",
      "#47 Loop (passed: 47/100):\n",
      "Proper answer: [-96, -90, -52, -48, -44, -39, -26, 19, 21, 23, 25, 33, 33, 43, 49, 51, 76]\n",
      "After sorting: [-96, -90, -52, -48, -44, -39, -26, 19, 21, 23, 25, 33, 33, 43, 49, 51, 76]\n",
      "\n",
      "#48 Loop (passed: 48/100):\n",
      "Proper answer: [-94, -87, -85, -70, -64, -62, -62, -60, -7, -4, 5, 6, 21, 22, 34, 43, 58, 71, 98]\n",
      "After sorting: [-94, -87, -85, -70, -64, -62, -62, -60, -7, -4, 5, 6, 21, 22, 34, 43, 58, 71, 98]\n",
      "\n",
      "#49 Loop (passed: 49/100):\n",
      "Proper answer: [-85, -60, -56, -48, -28, -23, -11, 1, 8, 15, 51, 57, 88]\n",
      "After sorting: [-85, -60, -56, -48, -28, -23, -11, 1, 8, 15, 51, 57, 88]\n",
      "\n",
      "#50 Loop (passed: 50/100):\n",
      "Proper answer: [-87, -3, 10, 22, 38, 42, 51, 69, 74, 78, 81, 85, 90]\n",
      "After sorting: [-87, -3, 10, 22, 38, 42, 51, 69, 74, 78, 81, 85, 90]\n",
      "\n",
      "#51 Loop (passed: 51/100):\n",
      "Proper answer: [-92, -89, -78, -76, -70, -62, -45, -42, -32, -29, -22, -2, 21, 28, 35, 37, 41, 52, 61, 66, 68]\n",
      "After sorting: [-92, -89, -78, -76, -70, -62, -45, -42, -32, -29, -22, -2, 21, 28, 35, 37, 41, 52, 61, 66, 68]\n",
      "\n",
      "#52 Loop (passed: 52/100):\n",
      "Proper answer: [-66, -63, -62, -18, 8, 11, 16, 29, 35, 93]\n",
      "After sorting: [-66, -63, -62, -18, 8, 11, 16, 29, 35, 93]\n",
      "\n",
      "#53 Loop (passed: 53/100):\n",
      "Proper answer: [-11, -6, 40, 54, 92]\n",
      "After sorting: [-11, -6, 40, 54, 92]\n",
      "\n",
      "#54 Loop (passed: 54/100):\n",
      "Proper answer: [-62, -21, 22, 63, 93]\n",
      "After sorting: [-62, -21, 22, 63, 93]\n",
      "\n",
      "#55 Loop (passed: 55/100):\n",
      "Proper answer: [-91, -73, -65, -38, -33, -23, 15, 22, 38, 53, 61, 74, 78, 87, 92, 96]\n",
      "After sorting: [-91, -73, -65, -38, -33, -23, 15, 22, 38, 53, 61, 74, 78, 87, 92, 96]\n",
      "\n",
      "#56 Loop (passed: 56/100):\n",
      "Proper answer: [-98, -98, -97, -77, -68, -41, -37, -36, -35, -30, -21, -18, -11, 1, 32, 48, 53, 57, 60, 64, 64, 77, 80, 86, 91, 96]\n",
      "After sorting: [-98, -98, -97, -77, -68, -41, -37, -36, -35, -30, -21, -18, -11, 1, 32, 48, 53, 57, 60, 64, 64, 77, 80, 86, 91, 96]\n",
      "\n",
      "#57 Loop (passed: 57/100):\n",
      "Proper answer: [-96, -85, -73, -67, -46, -30, -17, 5, 17, 32, 52, 58, 61, 79, 80, 82, 82, 88]\n",
      "After sorting: [-96, -85, -73, -67, -46, -30, -17, 5, 17, 32, 52, 58, 61, 79, 80, 82, 82, 88]\n",
      "\n",
      "#58 Loop (passed: 58/100):\n",
      "Proper answer: [-91, -82, -80, -67, -62, -49, -31, -28, -21, -14, -6, -5, 3, 29, 30, 33, 41, 54, 60, 60, 64, 95]\n",
      "After sorting: [-91, -82, -80, -67, -62, -49, -31, -28, -21, -14, -6, -5, 3, 29, 30, 33, 41, 54, 60, 60, 64, 95]\n",
      "\n",
      "#59 Loop (passed: 59/100):\n",
      "Proper answer: [-86, -50, -44, -43, -28, -21, -5, -3, 2, 11, 26, 40, 42, 47, 49, 53, 59, 69, 72, 83, 99]\n",
      "After sorting: [-86, -50, -44, -43, -28, -21, -5, -3, 2, 11, 26, 40, 42, 47, 49, 53, 59, 69, 72, 83, 99]\n",
      "\n",
      "#60 Loop (passed: 60/100):\n",
      "Proper answer: [-90, -87, -41, 13, 30, 30, 33, 38, 42, 91]\n",
      "After sorting: [-90, -87, -41, 13, 30, 30, 33, 38, 42, 91]\n",
      "\n",
      "#61 Loop (passed: 61/100):\n",
      "Proper answer: [-100, -46, -3, 43, 54, 57, 78]\n",
      "After sorting: [-100, -46, -3, 43, 54, 57, 78]\n",
      "\n",
      "#62 Loop (passed: 62/100):\n",
      "Proper answer: [-94, -46, -23, -5, 8, 14, 29, 38, 83]\n",
      "After sorting: [-94, -46, -23, -5, 8, 14, 29, 38, 83]\n",
      "\n",
      "#63 Loop (passed: 63/100):\n",
      "Proper answer: [-87, -65, -35, 42, 62, 74, 82, 89]\n",
      "After sorting: [-87, -65, -35, 42, 62, 74, 82, 89]\n",
      "\n",
      "#64 Loop (passed: 64/100):\n",
      "Proper answer: [-89, -86, -84, -74, -72, -45, -41, -32, -31, -27, -4, -3, 2, 24, 39, 48, 52, 54, 61, 71, 79, 91, 93, 94, 95, 100]\n",
      "After sorting: [-89, -86, -84, -74, -72, -45, -41, -32, -31, -27, -4, -3, 2, 24, 39, 48, 52, 54, 61, 71, 79, 91, 93, 94, 95, 100]\n",
      "\n",
      "#65 Loop (passed: 65/100):\n",
      "Proper answer: [-80, -49, -33, -26, -14, -9, 5, 14, 36, 50, 61]\n",
      "After sorting: [-80, -49, -33, -26, -14, -9, 5, 14, 36, 50, 61]\n",
      "\n",
      "#66 Loop (passed: 66/100):\n",
      "Proper answer: [-90, -90, -87, -83, -81, -80, -77, -75, -70, -60, -51, -37, -31, -19, -16, -7, 4, 4, 7, 14, 21, 29, 35, 49, 52, 52, 53, 100]\n",
      "After sorting: [-90, -90, -87, -83, -81, -80, -77, -75, -70, -60, -51, -37, -31, -19, -16, -7, 4, 4, 7, 14, 21, 29, 35, 49, 52, 52, 53, 100]\n",
      "\n",
      "#67 Loop (passed: 67/100):\n",
      "Proper answer: [-98, -66, -60, -55, -25, -18, -4, 17, 50, 65, 95]\n",
      "After sorting: [-98, -66, -60, -55, -25, -18, -4, 17, 50, 65, 95]\n",
      "\n",
      "#68 Loop (passed: 68/100):\n",
      "Proper answer: [-81, -73, -60, -59, -45, -44, 7, 11, 11, 30, 45, 48, 53, 65, 67, 69, 79, 86]\n",
      "After sorting: [-81, -73, -60, -59, -45, -44, 7, 11, 11, 30, 45, 48, 53, 65, 67, 69, 79, 86]\n",
      "\n",
      "#69 Loop (passed: 69/100):\n",
      "Proper answer: [-97, -96, -88, -84, -80, -80, -72, -68, -60, -49, -42, -37, -14, -13, -1, 6, 17, 23, 40, 43, 59, 60, 78, 85, 85]\n",
      "After sorting: [-97, -96, -88, -84, -80, -80, -72, -68, -60, -49, -42, -37, -14, -13, -1, 6, 17, 23, 40, 43, 59, 60, 78, 85, 85]\n",
      "\n",
      "#70 Loop (passed: 70/100):\n",
      "Proper answer: [-97, -88, -71, -70, -68, -58, -56, -44, -35, -28, -2, 1, 15, 37, 55, 55, 56, 82, 95]\n",
      "After sorting: [-97, -88, -71, -70, -68, -58, -56, -44, -35, -28, -2, 1, 15, 37, 55, 55, 56, 82, 95]\n",
      "\n",
      "#71 Loop (passed: 71/100):\n",
      "Proper answer: [-63, -30, -29, -22, -19, 8, 30, 68, 83]\n",
      "After sorting: [-63, -30, -29, -22, -19, 8, 30, 68, 83]\n",
      "\n",
      "#72 Loop (passed: 72/100):\n",
      "Proper answer: [-92, -89, -83, -82, -48, -46, -12, -9, -7, -3, 4, 13, 15, 17, 29, 29, 36, 45, 46, 51, 53, 54, 57, 62, 62, 74, 77, 80]\n",
      "After sorting: [-92, -89, -83, -82, -48, -46, -12, -9, -7, -3, 4, 13, 15, 17, 29, 29, 36, 45, 46, 51, 53, 54, 57, 62, 62, 74, 77, 80]\n",
      "\n",
      "#73 Loop (passed: 73/100):\n",
      "Proper answer: [-99, -99, -90, -73, -66, -56, 17, 27, 59, 77, 80, 86]\n",
      "After sorting: [-99, -99, -90, -73, -66, -56, 17, 27, 59, 77, 80, 86]\n",
      "\n",
      "#74 Loop (passed: 74/100):\n",
      "Proper answer: [-96, -89, -77, -71, -68, -63, -54, -51, -38, -30, 9, 13, 16, 17, 17, 27, 40, 41, 49, 54, 75, 85]\n",
      "After sorting: [-96, -89, -77, -71, -68, -63, -54, -51, -38, -30, 9, 13, 16, 17, 17, 27, 40, 41, 49, 54, 75, 85]\n",
      "\n",
      "#75 Loop (passed: 75/100):\n",
      "Proper answer: [-75, 15, 36, 47, 67]\n",
      "After sorting: [-75, 15, 36, 47, 67]\n",
      "\n",
      "#76 Loop (passed: 76/100):\n",
      "Proper answer: [-94, -93, -87, -85, -71, -63, -47, -33, -26, 2, 6, 6, 15, 21, 30, 50, 74, 79, 79, 91]\n",
      "After sorting: [-94, -93, -87, -85, -71, -63, -47, -33, -26, 2, 6, 6, 15, 21, 30, 50, 74, 79, 79, 91]\n",
      "\n",
      "#77 Loop (passed: 77/100):\n",
      "Proper answer: [-97, -81, -81, -74, -50, -38, -35, -16, -4, -4, 35, 52, 60, 81, 97, 98]\n",
      "After sorting: [-97, -81, -81, -74, -50, -38, -35, -16, -4, -4, 35, 52, 60, 81, 97, 98]\n",
      "\n",
      "#78 Loop (passed: 78/100):\n",
      "Proper answer: [-57, -45, -43, -33, -33, 8, 15, 16, 29, 30, 35, 46, 51, 54, 58, 75, 77, 90, 94, 99]\n",
      "After sorting: [-57, -45, -43, -33, -33, 8, 15, 16, 29, 30, 35, 46, 51, 54, 58, 75, 77, 90, 94, 99]\n",
      "\n",
      "#79 Loop (passed: 79/100):\n",
      "Proper answer: [-97, -91, -87, -84, -84, -56, -52, -38, -21, -14, -14, -13, 18, 21, 21, 33, 33, 46, 54, 55, 57, 62, 64, 68, 73, 94, 99]\n",
      "After sorting: [-97, -91, -87, -84, -84, -56, -52, -38, -21, -14, -14, -13, 18, 21, 21, 33, 33, 46, 54, 55, 57, 62, 64, 68, 73, 94, 99]\n",
      "\n",
      "#80 Loop (passed: 80/100):\n",
      "Proper answer: [-99, -99, -75, -64, -62, -62, -39, -35, -32, -17, 1, 12, 14, 19, 21, 25, 34, 35, 36, 37, 39, 50, 58, 64, 83, 94, 96]\n",
      "After sorting: [-99, -99, -75, -64, -62, -62, -39, -35, -32, -17, 1, 12, 14, 19, 21, 25, 34, 35, 36, 37, 39, 50, 58, 64, 83, 94, 96]\n",
      "\n",
      "#81 Loop (passed: 81/100):\n",
      "Proper answer: [-95, -95, -92, -80, -79, -78, -59, -55, -48, 10, 11, 14, 17, 17, 22, 24, 36, 40, 47, 58, 58, 65, 68, 76, 84, 93, 94, 95]\n",
      "After sorting: [-95, -95, -92, -80, -79, -78, -59, -55, -48, 10, 11, 14, 17, 17, 22, 24, 36, 40, 47, 58, 58, 65, 68, 76, 84, 93, 94, 95]\n",
      "\n",
      "#82 Loop (passed: 82/100):\n",
      "Proper answer: [-97, -91, -80, -72, -40, -38, -22, -4, -3, -1, 5, 8, 8, 10, 18, 21, 24, 31, 31, 53, 66, 68, 77, 86, 93]\n",
      "After sorting: [-97, -91, -80, -72, -40, -38, -22, -4, -3, -1, 5, 8, 8, 10, 18, 21, 24, 31, 31, 53, 66, 68, 77, 86, 93]\n",
      "\n",
      "#83 Loop (passed: 83/100):\n",
      "Proper answer: [-84, -17, -11, -8, -2, 10, 31, 36, 50, 68, 68, 86, 96]\n",
      "After sorting: [-84, -17, -11, -8, -2, 10, 31, 36, 50, 68, 68, 86, 96]\n",
      "\n",
      "#84 Loop (passed: 84/100):\n",
      "Proper answer: [-98, -93, -84, -81, -60, -50, -47, -26, -24, -14, -11, -11, 18, 20, 27, 40, 72, 74, 81, 88, 89]\n",
      "After sorting: [-98, -93, -84, -81, -60, -50, -47, -26, -24, -14, -11, -11, 18, 20, 27, 40, 72, 74, 81, 88, 89]\n",
      "\n",
      "#85 Loop (passed: 85/100):\n",
      "Proper answer: [-94, -86, -72, -65, -27, -6, -5, 8, 16, 66]\n",
      "After sorting: [-94, -86, -72, -65, -27, -6, -5, 8, 16, 66]\n",
      "\n",
      "#86 Loop (passed: 86/100):\n",
      "Proper answer: [-95, -88, -87, -81, -78, -77, -73, -53, -49, -43, -27, -25, -10, -9, 1, 9, 14, 19, 20, 21, 22, 28, 29, 32, 49, 66, 69, 73, 99]\n",
      "After sorting: [-95, -88, -87, -81, -78, -77, -73, -53, -49, -43, -27, -25, -10, -9, 1, 9, 14, 19, 20, 21, 22, 28, 29, 32, 49, 66, 69, 73, 99]\n",
      "\n",
      "#87 Loop (passed: 87/100):\n",
      "Proper answer: [14, 36, 53, 62, 71]\n",
      "After sorting: [14, 36, 53, 62, 71]\n",
      "\n",
      "#88 Loop (passed: 88/100):\n",
      "Proper answer: [-56, -32, 27, 34, 41, 56, 79]\n",
      "After sorting: [-56, -32, 27, 34, 41, 56, 79]\n",
      "\n",
      "#89 Loop (passed: 89/100):\n",
      "Proper answer: [-79, -68, -55, -51, -28, -26, -26, -17, -11, 45, 73, 90, 93]\n",
      "After sorting: [-79, -68, -55, -51, -28, -26, -26, -17, -11, 45, 73, 90, 93]\n",
      "\n",
      "#90 Loop (passed: 90/100):\n",
      "Proper answer: [-97, -88, -86, -81, -80, -71, -69, -38, -37, -25, -18, -15, 28, 32, 34, 34, 37, 44, 59, 72, 75, 76, 83, 86, 87, 100]\n",
      "After sorting: [-97, -88, -86, -81, -80, -71, -69, -38, -37, -25, -18, -15, 28, 32, 34, 34, 37, 44, 59, 72, 75, 76, 83, 86, 87, 100]\n",
      "\n",
      "#91 Loop (passed: 91/100):\n",
      "Proper answer: [-68, -67, -65, -60, -50, -46, -28, -22, -17, 4, 16, 18, 46, 60, 94]\n",
      "After sorting: [-68, -67, -65, -60, -50, -46, -28, -22, -17, 4, 16, 18, 46, 60, 94]\n",
      "\n",
      "#92 Loop (passed: 92/100):\n",
      "Proper answer: [-99, -91, -85, -82, -82, -59, -58, -57, -46, -35, -23, -21, -16, -1, 4, 38, 45, 46, 70, 88, 89, 91]\n",
      "After sorting: [-99, -91, -85, -82, -82, -59, -58, -57, -46, -35, -23, -21, -16, -1, 4, 38, 45, 46, 70, 88, 89, 91]\n",
      "\n",
      "#93 Loop (passed: 93/100):\n",
      "Proper answer: [-99, -76, -11, 21, 38]\n",
      "After sorting: [-99, -76, -11, 21, 38]\n",
      "\n",
      "#94 Loop (passed: 94/100):\n",
      "Proper answer: [-99, -97, -95, -95, -87, -82, -81, -68, -67, -66, -49, -19, -8, -6, 0, 1, 2, 22, 32, 35, 42, 45, 53, 54, 61, 98]\n",
      "After sorting: [-99, -97, -95, -95, -87, -82, -81, -68, -67, -66, -49, -19, -8, -6, 0, 1, 2, 22, 32, 35, 42, 45, 53, 54, 61, 98]\n",
      "\n",
      "#95 Loop (passed: 95/100):\n",
      "Proper answer: [-96, -87, -84, -59, -58, -53, -51, -50, -42, -31, -27, -13, -4, 6, 16, 17, 21, 39, 46, 48, 53, 63, 69, 87, 90]\n",
      "After sorting: [-96, -87, -84, -59, -58, -53, -51, -50, -42, -31, -27, -13, -4, 6, 16, 17, 21, 39, 46, 48, 53, 63, 69, 87, 90]\n",
      "\n",
      "#96 Loop (passed: 96/100):\n",
      "Proper answer: [-99, -92, -85, -76, -54, -34, -32, 0, 5, 15, 24, 29, 34, 36, 72, 78]\n",
      "After sorting: [-99, -92, -85, -76, -54, -34, -32, 0, 5, 15, 24, 29, 34, 36, 72, 78]\n",
      "\n",
      "#97 Loop (passed: 97/100):\n",
      "Proper answer: [-91, -88, -78, -76, -51, -48, -30, -15, -13, 3, 13, 25, 50, 67, 78, 97, 98, 99]\n",
      "After sorting: [-91, -88, -78, -76, -51, -48, -30, -15, -13, 3, 13, 25, 50, 67, 78, 97, 98, 99]\n",
      "\n",
      "#98 Loop (passed: 98/100):\n",
      "Proper answer: [-89, -68, -67, -67, -59, -53, -49, -40, -17, 4, 14, 18, 22, 28, 37, 39, 41, 50, 69, 71, 77, 79, 84, 96, 97, 98]\n",
      "After sorting: [-89, -68, -67, -67, -59, -53, -49, -40, -17, 4, 14, 18, 22, 28, 37, 39, 41, 50, 69, 71, 77, 79, 84, 96, 97, 98]\n",
      "\n",
      "#99 Loop (passed: 99/100):\n",
      "Proper answer: [-98, -13, -12, 11, 85, 98]\n",
      "After sorting: [-98, -13, -12, 11, 85, 98]\n",
      "\n",
      "#100 Loop (passed: 100/100):\n",
      "Proper answer: [-18, -14, -13, -4, 7, 34, 44, 65, 81]\n",
      "After sorting: [-18, -14, -13, -4, 7, 34, 44, 65, 81]\n",
      "\n",
      "Total passed tests: 100/100\n",
      "A sorting algorithm is implemented correctly\n"
     ]
    }
   ],
   "source": [
    "test_sort(insertion_sort, samples=100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### #4 b) sortowanie przez wybieranie"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def selection_sort(ll):\n",
    "    if len(ll) < 2: return\n",
    "    \n",
    "    first = ll.head\n",
    "    \n",
    "    # Loop while a first pointer is not the last element\n",
    "    while first.next:\n",
    "        min_node = first\n",
    "        second = first.next\n",
    "        while second:\n",
    "            # Look for a currently minimal value\n",
    "            if second.val < min_node.val:\n",
    "                min_node = second\n",
    "            second = second.next\n",
    "        # Swap values in order to make them sorted\n",
    "        min_node.val, first.val = first.val, min_node.val\n",
    "        first = first.next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Przykładowy test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#1 Loop (passed: 1/100):\n",
      "Proper answer: [-93, -92, -91, -80, -56, -55, -36, -25, -25, 2, 7, 13, 29, 31, 36, 44, 46, 48, 51, 89, 89, 91, 92]\n",
      "After sorting: [-93, -92, -91, -80, -56, -55, -36, -25, -25, 2, 7, 13, 29, 31, 36, 44, 46, 48, 51, 89, 89, 91, 92]\n",
      "\n",
      "#2 Loop (passed: 2/100):\n",
      "Proper answer: [-94, -80, -77, -75, -62, -54, -47, -37, -28, -7, 9, 11, 11, 17, 22, 26, 32, 33, 33, 37, 43, 44, 45, 52, 71, 81, 83, 95, 95]\n",
      "After sorting: [-94, -80, -77, -75, -62, -54, -47, -37, -28, -7, 9, 11, 11, 17, 22, 26, 32, 33, 33, 37, 43, 44, 45, 52, 71, 81, 83, 95, 95]\n",
      "\n",
      "#3 Loop (passed: 3/100):\n",
      "Proper answer: [-89, -77, -74, -73, -70, -68, -67, -58, -51, -50, -25, -17, -13, -9, -9, -6, 0, 15, 31, 40, 50, 52, 68, 84]\n",
      "After sorting: [-89, -77, -74, -73, -70, -68, -67, -58, -51, -50, -25, -17, -13, -9, -9, -6, 0, 15, 31, 40, 50, 52, 68, 84]\n",
      "\n",
      "#4 Loop (passed: 4/100):\n",
      "Proper answer: [-93, -92, -83, -78, -75, -69, -61, -54, -46, -44, -39, -36, -33, -30, -6, -6, 1, 8, 29, 38, 45, 59, 74, 75, 80]\n",
      "After sorting: [-93, -92, -83, -78, -75, -69, -61, -54, -46, -44, -39, -36, -33, -30, -6, -6, 1, 8, 29, 38, 45, 59, 74, 75, 80]\n",
      "\n",
      "#5 Loop (passed: 5/100):\n",
      "Proper answer: [-80, -64, -57, -53, -24, -18, -4, 20, 23, 47, 64, 73, 81, 87, 88, 88]\n",
      "After sorting: [-80, -64, -57, -53, -24, -18, -4, 20, 23, 47, 64, 73, 81, 87, 88, 88]\n",
      "\n",
      "#6 Loop (passed: 6/100):\n",
      "Proper answer: [-65, 3, 10, 18, 91]\n",
      "After sorting: [-65, 3, 10, 18, 91]\n",
      "\n",
      "#7 Loop (passed: 7/100):\n",
      "Proper answer: [-36, -35, -21, -1, 7, 14, 35, 39, 48]\n",
      "After sorting: [-36, -35, -21, -1, 7, 14, 35, 39, 48]\n",
      "\n",
      "#8 Loop (passed: 8/100):\n",
      "Proper answer: [-75, -73, -66, -64, -45, -42, -25, -7, 8, 21, 23, 60, 64, 67, 76, 78, 79, 88, 94]\n",
      "After sorting: [-75, -73, -66, -64, -45, -42, -25, -7, 8, 21, 23, 60, 64, 67, 76, 78, 79, 88, 94]\n",
      "\n",
      "#9 Loop (passed: 9/100):\n",
      "Proper answer: [-45, 10, 37, 67, 81, 88, 92]\n",
      "After sorting: [-45, 10, 37, 67, 81, 88, 92]\n",
      "\n",
      "#10 Loop (passed: 10/100):\n",
      "Proper answer: [-96, -81, -69, -48, -33, -33, 1, 5, 21, 38, 67, 84]\n",
      "After sorting: [-96, -81, -69, -48, -33, -33, 1, 5, 21, 38, 67, 84]\n",
      "\n",
      "#11 Loop (passed: 11/100):\n",
      "Proper answer: [-87, -87, -80, -44, -1, 51, 54, 67, 72]\n",
      "After sorting: [-87, -87, -80, -44, -1, 51, 54, 67, 72]\n",
      "\n",
      "#12 Loop (passed: 12/100):\n",
      "Proper answer: [-100, -97, -88, -85, -85, -73, -60, -60, -45, -28, -17, -2, 6, 7, 16, 18, 36, 49, 54, 60]\n",
      "After sorting: [-100, -97, -88, -85, -85, -73, -60, -60, -45, -28, -17, -2, 6, 7, 16, 18, 36, 49, 54, 60]\n",
      "\n",
      "#13 Loop (passed: 13/100):\n",
      "Proper answer: [-98, -92, -58, -53, -47, -17, -15, -3, 29, 33, 44, 70, 87, 88, 89]\n",
      "After sorting: [-98, -92, -58, -53, -47, -17, -15, -3, 29, 33, 44, 70, 87, 88, 89]\n",
      "\n",
      "#14 Loop (passed: 14/100):\n",
      "Proper answer: [-85, -82, -78, -75, -66, -13, 33, 35, 54, 58, 75, 94, 96, 98]\n",
      "After sorting: [-85, -82, -78, -75, -66, -13, 33, 35, 54, 58, 75, 94, 96, 98]\n",
      "\n",
      "#15 Loop (passed: 15/100):\n",
      "Proper answer: [-92, -89, -87, -82, -68, -53, -46, -30, -29, -24, -18, -7, -1, 11, 23, 28, 32, 52, 54, 79, 81, 92, 99, 100]\n",
      "After sorting: [-92, -89, -87, -82, -68, -53, -46, -30, -29, -24, -18, -7, -1, 11, 23, 28, 32, 52, 54, 79, 81, 92, 99, 100]\n",
      "\n",
      "#16 Loop (passed: 16/100):\n",
      "Proper answer: [-85, -65, -64, 3, 19, 78, 85]\n",
      "After sorting: [-85, -65, -64, 3, 19, 78, 85]\n",
      "\n",
      "#17 Loop (passed: 17/100):\n",
      "Proper answer: [-97, -62, -60, 4, 22, 45, 47, 69, 75]\n",
      "After sorting: [-97, -62, -60, 4, 22, 45, 47, 69, 75]\n",
      "\n",
      "#18 Loop (passed: 18/100):\n",
      "Proper answer: [-72, -71, -58, -49, -45, -17, 27, 76, 83, 87, 98]\n",
      "After sorting: [-72, -71, -58, -49, -45, -17, 27, 76, 83, 87, 98]\n",
      "\n",
      "#19 Loop (passed: 19/100):\n",
      "Proper answer: [-100, -76, -70, -63, -54, -52, -47, -47, -38, -36, -18, -6, -5, -2, 2, 2, 6, 14, 15, 16, 18, 30, 39, 44, 48, 53, 63, 67, 71]\n",
      "After sorting: [-100, -76, -70, -63, -54, -52, -47, -47, -38, -36, -18, -6, -5, -2, 2, 2, 6, 14, 15, 16, 18, 30, 39, 44, 48, 53, 63, 67, 71]\n",
      "\n",
      "#20 Loop (passed: 20/100):\n",
      "Proper answer: [-84, -74, -37, -19, -7, 12, 12, 36, 36, 38, 40, 45, 46, 62, 73, 75, 77, 85]\n",
      "After sorting: [-84, -74, -37, -19, -7, 12, 12, 36, 36, 38, 40, 45, 46, 62, 73, 75, 77, 85]\n",
      "\n",
      "#21 Loop (passed: 21/100):\n",
      "Proper answer: [-92, -72, 5, 50, 56, 75, 87]\n",
      "After sorting: [-92, -72, 5, 50, 56, 75, 87]\n",
      "\n",
      "#22 Loop (passed: 22/100):\n",
      "Proper answer: [-96, -95, -95, -90, -85, -64, -62, -31, -25, -23, -22, -22, -19, 8, 21, 40, 66, 70, 71, 71]\n",
      "After sorting: [-96, -95, -95, -90, -85, -64, -62, -31, -25, -23, -22, -22, -19, 8, 21, 40, 66, 70, 71, 71]\n",
      "\n",
      "#23 Loop (passed: 23/100):\n",
      "Proper answer: [-90, -83, -82, -64, -63, 49, 57, 62, 77, 90]\n",
      "After sorting: [-90, -83, -82, -64, -63, 49, 57, 62, 77, 90]\n",
      "\n",
      "#24 Loop (passed: 24/100):\n",
      "Proper answer: [-42, -2, 10, 12, 56, 100]\n",
      "After sorting: [-42, -2, 10, 12, 56, 100]\n",
      "\n",
      "#25 Loop (passed: 25/100):\n",
      "Proper answer: [-97, -72, -62, -51, -49, -47, -30, -6, 0, 11, 16, 35, 42, 59, 59, 63, 70, 85, 92, 97, 99]\n",
      "After sorting: [-97, -72, -62, -51, -49, -47, -30, -6, 0, 11, 16, 35, 42, 59, 59, 63, 70, 85, 92, 97, 99]\n",
      "\n",
      "#26 Loop (passed: 26/100):\n",
      "Proper answer: [-97, -94, -85, -65, -41, -38, -30, -19, -16, -9, -4, 11, 32, 41, 65, 81, 87]\n",
      "After sorting: [-97, -94, -85, -65, -41, -38, -30, -19, -16, -9, -4, 11, 32, 41, 65, 81, 87]\n",
      "\n",
      "#27 Loop (passed: 27/100):\n",
      "Proper answer: [-97, -88, -83, -76, -72, -67, -46, -42, -41, -35, -21, -5, -1, 3, 8, 23, 24, 27, 30, 47, 51, 54, 72, 80, 85, 98]\n",
      "After sorting: [-97, -88, -83, -76, -72, -67, -46, -42, -41, -35, -21, -5, -1, 3, 8, 23, 24, 27, 30, 47, 51, 54, 72, 80, 85, 98]\n",
      "\n",
      "#28 Loop (passed: 28/100):\n",
      "Proper answer: [-89, -56, -52, -32, -16, 4]\n",
      "After sorting: [-89, -56, -52, -32, -16, 4]\n",
      "\n",
      "#29 Loop (passed: 29/100):\n",
      "Proper answer: [-89, -84, -80, -72, -69, -60, -43, -39, -35, -30, -22, -22, -22, -13, -7, -5, -1, 2, 4, 10, 18, 33, 39, 55, 56, 59, 75, 77]\n",
      "After sorting: [-89, -84, -80, -72, -69, -60, -43, -39, -35, -30, -22, -22, -22, -13, -7, -5, -1, 2, 4, 10, 18, 33, 39, 55, 56, 59, 75, 77]\n",
      "\n",
      "#30 Loop (passed: 30/100):\n",
      "Proper answer: [-85, -84, -82, -67, -59, -57, -38, -15, -9, -1, 10, 19, 19, 28, 49, 51, 57, 59, 60, 75, 79]\n",
      "After sorting: [-85, -84, -82, -67, -59, -57, -38, -15, -9, -1, 10, 19, 19, 28, 49, 51, 57, 59, 60, 75, 79]\n",
      "\n",
      "#31 Loop (passed: 31/100):\n",
      "Proper answer: [-99, -93, -76, -73, -72, -70, -69, -51, -51, -37, -29, -19, -17, -16, -15, -15, 8, 9, 32, 39, 43, 57, 63, 71, 82, 89, 91, 95, 98]\n",
      "After sorting: [-99, -93, -76, -73, -72, -70, -69, -51, -51, -37, -29, -19, -17, -16, -15, -15, 8, 9, 32, 39, 43, 57, 63, 71, 82, 89, 91, 95, 98]\n",
      "\n",
      "#32 Loop (passed: 32/100):\n",
      "Proper answer: [-83, -77, -71, -68, -65, -48, -46, -44, -29, -11, -3, 2, 4, 12, 16, 16, 31, 50, 50, 55, 86, 94, 95]\n",
      "After sorting: [-83, -77, -71, -68, -65, -48, -46, -44, -29, -11, -3, 2, 4, 12, 16, 16, 31, 50, 50, 55, 86, 94, 95]\n",
      "\n",
      "#33 Loop (passed: 33/100):\n",
      "Proper answer: [-92, -73, -55, -52, -48, -38, -10, 17, 33, 44, 62, 82, 100]\n",
      "After sorting: [-92, -73, -55, -52, -48, -38, -10, 17, 33, 44, 62, 82, 100]\n",
      "\n",
      "#34 Loop (passed: 34/100):\n",
      "Proper answer: [-97, -97, -92, -79, -77, -76, -76, -74, -61, -42, -41, -33, -26, -20, -3, 10, 13, 26, 54, 64, 64, 69]\n",
      "After sorting: [-97, -97, -92, -79, -77, -76, -76, -74, -61, -42, -41, -33, -26, -20, -3, 10, 13, 26, 54, 64, 64, 69]\n",
      "\n",
      "#35 Loop (passed: 35/100):\n",
      "Proper answer: [-95, -88, -77, -38, -37, -21, -9, 22, 32, 48, 53, 72, 74, 84]\n",
      "After sorting: [-95, -88, -77, -38, -37, -21, -9, 22, 32, 48, 53, 72, 74, 84]\n",
      "\n",
      "#36 Loop (passed: 36/100):\n",
      "Proper answer: [-36, -19, 55, 69, 76, 78, 92, 96]\n",
      "After sorting: [-36, -19, 55, 69, 76, 78, 92, 96]\n",
      "\n",
      "#37 Loop (passed: 37/100):\n",
      "Proper answer: [-90, -87, -41, -37, -20, -18, -15, -7, 4, 13, 16, 18, 22, 24, 55, 62, 75, 77, 83, 87]\n",
      "After sorting: [-90, -87, -41, -37, -20, -18, -15, -7, 4, 13, 16, 18, 22, 24, 55, 62, 75, 77, 83, 87]\n",
      "\n",
      "#38 Loop (passed: 38/100):\n",
      "Proper answer: [-100, -95, -95, -77, -65, -43, -37, -27, -26, -19, -18, -11, -8, 10, 11, 15, 15, 25, 61, 64, 74, 77, 82, 85, 85, 88, 92, 99, 99]\n",
      "After sorting: [-100, -95, -95, -77, -65, -43, -37, -27, -26, -19, -18, -11, -8, 10, 11, 15, 15, 25, 61, 64, 74, 77, 82, 85, 85, 88, 92, 99, 99]\n",
      "\n",
      "#39 Loop (passed: 39/100):\n",
      "Proper answer: [-77, -54, -42, 17, 34, 59, 75, 80]\n",
      "After sorting: [-77, -54, -42, 17, 34, 59, 75, 80]\n",
      "\n",
      "#40 Loop (passed: 40/100):\n",
      "Proper answer: [-71, -66, -59, -45, -35, -33, -32, -27, -18, -15, -8, -4, 6, 13, 21, 45, 53, 79, 80, 100]\n",
      "After sorting: [-71, -66, -59, -45, -35, -33, -32, -27, -18, -15, -8, -4, 6, 13, 21, 45, 53, 79, 80, 100]\n",
      "\n",
      "#41 Loop (passed: 41/100):\n",
      "Proper answer: [-88, -70, -50, -39, -6, -4, 14, 33, 49, 76, 82, 88]\n",
      "After sorting: [-88, -70, -50, -39, -6, -4, 14, 33, 49, 76, 82, 88]\n",
      "\n",
      "#42 Loop (passed: 42/100):\n",
      "Proper answer: [-96, -80, -45, -44, -41, -17, 4, 13, 32, 45, 67, 72, 88]\n",
      "After sorting: [-96, -80, -45, -44, -41, -17, 4, 13, 32, 45, 67, 72, 88]\n",
      "\n",
      "#43 Loop (passed: 43/100):\n",
      "Proper answer: [-99, -99, -76, -75, -61, -59, -52, -45, -41, -40, -37, -26, -25, -22, -4, 0, 10, 21, 29, 47, 73, 84, 90, 97]\n",
      "After sorting: [-99, -99, -76, -75, -61, -59, -52, -45, -41, -40, -37, -26, -25, -22, -4, 0, 10, 21, 29, 47, 73, 84, 90, 97]\n",
      "\n",
      "#44 Loop (passed: 44/100):\n",
      "Proper answer: [-80, -73, -23, -15, -8, -8, 27, 68, 97]\n",
      "After sorting: [-80, -73, -23, -15, -8, -8, 27, 68, 97]\n",
      "\n",
      "#45 Loop (passed: 45/100):\n",
      "Proper answer: [-81, -57, -26, -19, -7, 1, 2, 4, 8, 14, 25, 48, 56, 65, 69]\n",
      "After sorting: [-81, -57, -26, -19, -7, 1, 2, 4, 8, 14, 25, 48, 56, 65, 69]\n",
      "\n",
      "#46 Loop (passed: 46/100):\n",
      "Proper answer: [-100, -98, -97, -84, -78, -74, -65, -63, -49, -47, -46, -42, -24, -21, -5, 2, 4, 26, 27, 32, 33, 33, 35, 48, 50, 63, 87]\n",
      "After sorting: [-100, -98, -97, -84, -78, -74, -65, -63, -49, -47, -46, -42, -24, -21, -5, 2, 4, 26, 27, 32, 33, 33, 35, 48, 50, 63, 87]\n",
      "\n",
      "#47 Loop (passed: 47/100):\n",
      "Proper answer: [-97, -96, -86, -84, -76, -65, -60, -59, -45, 23, 24, 30, 32, 34, 36, 44, 51, 52, 60, 66, 71, 71, 84, 89, 92]\n",
      "After sorting: [-97, -96, -86, -84, -76, -65, -60, -59, -45, 23, 24, 30, 32, 34, 36, 44, 51, 52, 60, 66, 71, 71, 84, 89, 92]\n",
      "\n",
      "#48 Loop (passed: 48/100):\n",
      "Proper answer: [-87, -77, -52, -40, -23, -12, -4, 19, 25, 40, 45, 53]\n",
      "After sorting: [-87, -77, -52, -40, -23, -12, -4, 19, 25, 40, 45, 53]\n",
      "\n",
      "#49 Loop (passed: 49/100):\n",
      "Proper answer: [-100, -63, -16, -15, -13, -6, -2, 34, 63, 85, 92, 100]\n",
      "After sorting: [-100, -63, -16, -15, -13, -6, -2, 34, 63, 85, 92, 100]\n",
      "\n",
      "#50 Loop (passed: 50/100):\n",
      "Proper answer: [-64, -43, -22, 13, 14, 25, 59, 71]\n",
      "After sorting: [-64, -43, -22, 13, 14, 25, 59, 71]\n",
      "\n",
      "#51 Loop (passed: 51/100):\n",
      "Proper answer: [-97, -96, -75, -45, -40, -37, -35, 19, 32, 69, 99]\n",
      "After sorting: [-97, -96, -75, -45, -40, -37, -35, 19, 32, 69, 99]\n",
      "\n",
      "#52 Loop (passed: 52/100):\n",
      "Proper answer: [-63, -52, -37, -26, 28, 43, 56, 58, 61, 65, 65, 71, 79, 82, 100]\n",
      "After sorting: [-63, -52, -37, -26, 28, 43, 56, 58, 61, 65, 65, 71, 79, 82, 100]\n",
      "\n",
      "#53 Loop (passed: 53/100):\n",
      "Proper answer: [-85, -48, -35, 7, 16]\n",
      "After sorting: [-85, -48, -35, 7, 16]\n",
      "\n",
      "#54 Loop (passed: 54/100):\n",
      "Proper answer: [-36, -35, -19, 2, 7, 50, 51, 55, 93, 96]\n",
      "After sorting: [-36, -35, -19, 2, 7, 50, 51, 55, 93, 96]\n",
      "\n",
      "#55 Loop (passed: 55/100):\n",
      "Proper answer: [-99, -93, -89, -80, -74, -63, -56, -49, -37, -29, -6, 5, 11, 67, 68, 69, 82, 84, 93, 93, 95, 98]\n",
      "After sorting: [-99, -93, -89, -80, -74, -63, -56, -49, -37, -29, -6, 5, 11, 67, 68, 69, 82, 84, 93, 93, 95, 98]\n",
      "\n",
      "#56 Loop (passed: 56/100):\n",
      "Proper answer: [-90, -62, -56, -36, -8, 4, 5, 58, 60, 62, 74, 85]\n",
      "After sorting: [-90, -62, -56, -36, -8, 4, 5, 58, 60, 62, 74, 85]\n",
      "\n",
      "#57 Loop (passed: 57/100):\n",
      "Proper answer: [-97, -92, -92, -87, -63, -54, -42, -40, -40, -37, -36, -32, -30, 0, 7, 15, 34, 54, 70, 73]\n",
      "After sorting: [-97, -92, -92, -87, -63, -54, -42, -40, -40, -37, -36, -32, -30, 0, 7, 15, 34, 54, 70, 73]\n",
      "\n",
      "#58 Loop (passed: 58/100):\n",
      "Proper answer: [-61, -60, -7, -6, 36, 41, 76]\n",
      "After sorting: [-61, -60, -7, -6, 36, 41, 76]\n",
      "\n",
      "#59 Loop (passed: 59/100):\n",
      "Proper answer: [-84, -80, -34, 52, 60]\n",
      "After sorting: [-84, -80, -34, 52, 60]\n",
      "\n",
      "#60 Loop (passed: 60/100):\n",
      "Proper answer: [-98, -96, -95, -85, -52, -40, -23, -11, 0, 1, 2, 21, 62, 87, 89]\n",
      "After sorting: [-98, -96, -95, -85, -52, -40, -23, -11, 0, 1, 2, 21, 62, 87, 89]\n",
      "\n",
      "#61 Loop (passed: 61/100):\n",
      "Proper answer: [-99, -95, -84, -83, -82, -82, -58, -57, -47, -36, -32, -27, -22, 4, 5, 11, 41, 54, 59, 64, 76, 88, 90]\n",
      "After sorting: [-99, -95, -84, -83, -82, -82, -58, -57, -47, -36, -32, -27, -22, 4, 5, 11, 41, 54, 59, 64, 76, 88, 90]\n",
      "\n",
      "#62 Loop (passed: 62/100):\n",
      "Proper answer: [-80, -74, -63, -39, -33, -15, -14, -1, 2, 5, 17, 38, 40, 48, 54]\n",
      "After sorting: [-80, -74, -63, -39, -33, -15, -14, -1, 2, 5, 17, 38, 40, 48, 54]\n",
      "\n",
      "#63 Loop (passed: 63/100):\n",
      "Proper answer: [-73, -66, -59, -58, -31, -7, -5, -3, -3, 3, 3, 5, 7, 7, 17, 27, 34, 39, 40, 41, 42, 45, 55, 61, 77, 83, 85, 91, 94, 97]\n",
      "After sorting: [-73, -66, -59, -58, -31, -7, -5, -3, -3, 3, 3, 5, 7, 7, 17, 27, 34, 39, 40, 41, 42, 45, 55, 61, 77, 83, 85, 91, 94, 97]\n",
      "\n",
      "#64 Loop (passed: 64/100):\n",
      "Proper answer: [-88, -69, -68, -66, -52, -50, 16, 43, 66, 72, 81, 93]\n",
      "After sorting: [-88, -69, -68, -66, -52, -50, 16, 43, 66, 72, 81, 93]\n",
      "\n",
      "#65 Loop (passed: 65/100):\n",
      "Proper answer: [-79, -79, -71, -70, -64, -39, -31, -26, -7, 1, 2, 4, 30, 32, 35, 39, 43, 65, 89, 90, 93, 93, 100]\n",
      "After sorting: [-79, -79, -71, -70, -64, -39, -31, -26, -7, 1, 2, 4, 30, 32, 35, 39, 43, 65, 89, 90, 93, 93, 100]\n",
      "\n",
      "#66 Loop (passed: 66/100):\n",
      "Proper answer: [-87, -74, -68, -36, -34, -28, -22, -13, 15, 31, 44, 49, 50, 54, 58, 62, 67, 81, 82]\n",
      "After sorting: [-87, -74, -68, -36, -34, -28, -22, -13, 15, 31, 44, 49, 50, 54, 58, 62, 67, 81, 82]\n",
      "\n",
      "#67 Loop (passed: 67/100):\n",
      "Proper answer: [-98, -98, -91, -76, -74, -70, -66, -59, -50, -43, -40, -35, -32, -11, -1, 4, 9, 14, 28, 33, 34, 48, 48, 60, 61, 70, 83, 85, 88, 95]\n",
      "After sorting: [-98, -98, -91, -76, -74, -70, -66, -59, -50, -43, -40, -35, -32, -11, -1, 4, 9, 14, 28, 33, 34, 48, 48, 60, 61, 70, 83, 85, 88, 95]\n",
      "\n",
      "#68 Loop (passed: 68/100):\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Proper answer: [-92, -70, -1, -1, 3, 4, 7, 41, 53, 67, 80, 99]\n",
      "After sorting: [-92, -70, -1, -1, 3, 4, 7, 41, 53, 67, 80, 99]\n",
      "\n",
      "#69 Loop (passed: 69/100):\n",
      "Proper answer: [-78, -70, -54, -53, -50, -46, -43, -42, -29, -12, -9, 8, 10, 10, 20, 22, 34, 35, 53, 62, 63, 75, 81, 82]\n",
      "After sorting: [-78, -70, -54, -53, -50, -46, -43, -42, -29, -12, -9, 8, 10, 10, 20, 22, 34, 35, 53, 62, 63, 75, 81, 82]\n",
      "\n",
      "#70 Loop (passed: 70/100):\n",
      "Proper answer: [-88, -79, -78, -72, -64, -49, -42, -21, 5, 26, 66, 80, 87, 88, 88]\n",
      "After sorting: [-88, -79, -78, -72, -64, -49, -42, -21, 5, 26, 66, 80, 87, 88, 88]\n",
      "\n",
      "#71 Loop (passed: 71/100):\n",
      "Proper answer: [-99, -65, -46, -10, -6, 8, 18, 87]\n",
      "After sorting: [-99, -65, -46, -10, -6, 8, 18, 87]\n",
      "\n",
      "#72 Loop (passed: 72/100):\n",
      "Proper answer: [-86, -81, -74, -69, -65, -63, -55, -54, -52, -50, -46, -29, -29, -23, -21, -19, -17, 6, 7, 40, 44, 52, 60, 64, 67, 77, 87, 90, 99]\n",
      "After sorting: [-86, -81, -74, -69, -65, -63, -55, -54, -52, -50, -46, -29, -29, -23, -21, -19, -17, 6, 7, 40, 44, 52, 60, 64, 67, 77, 87, 90, 99]\n",
      "\n",
      "#73 Loop (passed: 73/100):\n",
      "Proper answer: [-75, -20, -4, 7, 23, 30, 33, 36, 72, 90]\n",
      "After sorting: [-75, -20, -4, 7, 23, 30, 33, 36, 72, 90]\n",
      "\n",
      "#74 Loop (passed: 74/100):\n",
      "Proper answer: [-100, -98, -85, -78, -72, -66, -39, -38, -17, -11, -3, 8, 26, 28, 45, 46, 50, 57, 86]\n",
      "After sorting: [-100, -98, -85, -78, -72, -66, -39, -38, -17, -11, -3, 8, 26, 28, 45, 46, 50, 57, 86]\n",
      "\n",
      "#75 Loop (passed: 75/100):\n",
      "Proper answer: [-9, 76, 81, 82, 98]\n",
      "After sorting: [-9, 76, 81, 82, 98]\n",
      "\n",
      "#76 Loop (passed: 76/100):\n",
      "Proper answer: [-92, -82, -77, -56, -53, -52, -35, -5, 11, 12, 28, 74, 77, 99]\n",
      "After sorting: [-92, -82, -77, -56, -53, -52, -35, -5, 11, 12, 28, 74, 77, 99]\n",
      "\n",
      "#77 Loop (passed: 77/100):\n",
      "Proper answer: [-97, -96, -93, -92, -90, -58, -47, -41, -35, -30, -3, 22, 30, 32, 46, 57, 67, 68, 69, 76, 76, 84]\n",
      "After sorting: [-97, -96, -93, -92, -90, -58, -47, -41, -35, -30, -3, 22, 30, 32, 46, 57, 67, 68, 69, 76, 76, 84]\n",
      "\n",
      "#78 Loop (passed: 78/100):\n",
      "Proper answer: [-99, -73, -45, -43, -24, -11, -8, 4, 30, 59, 80, 82, 92, 98]\n",
      "After sorting: [-99, -73, -45, -43, -24, -11, -8, 4, 30, 59, 80, 82, 92, 98]\n",
      "\n",
      "#79 Loop (passed: 79/100):\n",
      "Proper answer: [-100, -67, -67, -65, -58, -51, -11, -2, 4, 47, 84, 92, 99]\n",
      "After sorting: [-100, -67, -67, -65, -58, -51, -11, -2, 4, 47, 84, 92, 99]\n",
      "\n",
      "#80 Loop (passed: 80/100):\n",
      "Proper answer: [-86, -65, -61, -57, -53, -28, -28, -1, 3, 5, 13, 34, 45, 50, 50, 53, 74, 76, 85, 92]\n",
      "After sorting: [-86, -65, -61, -57, -53, -28, -28, -1, 3, 5, 13, 34, 45, 50, 50, 53, 74, 76, 85, 92]\n",
      "\n",
      "#81 Loop (passed: 81/100):\n",
      "Proper answer: [-96, -94, -92, -90, -54, -38, -34, -31, -24, -21, -4, -2, -2, 23, 34, 44, 70, 71, 78, 85, 98]\n",
      "After sorting: [-96, -94, -92, -90, -54, -38, -34, -31, -24, -21, -4, -2, -2, 23, 34, 44, 70, 71, 78, 85, 98]\n",
      "\n",
      "#82 Loop (passed: 82/100):\n",
      "Proper answer: [-70, -54, 7, 40, 51, 76, 79, 95]\n",
      "After sorting: [-70, -54, 7, 40, 51, 76, 79, 95]\n",
      "\n",
      "#83 Loop (passed: 83/100):\n",
      "Proper answer: [-100, -98, -82, -78, -75, -68, -52, -32, -32, -21, -16, -15, -1, 11, 12, 49, 53, 68, 85]\n",
      "After sorting: [-100, -98, -82, -78, -75, -68, -52, -32, -32, -21, -16, -15, -1, 11, 12, 49, 53, 68, 85]\n",
      "\n",
      "#84 Loop (passed: 84/100):\n",
      "Proper answer: [-96, -50, -47, -47, -23, 23, 36, 40, 55, 55, 67, 73, 89]\n",
      "After sorting: [-96, -50, -47, -47, -23, 23, 36, 40, 55, 55, 67, 73, 89]\n",
      "\n",
      "#85 Loop (passed: 85/100):\n",
      "Proper answer: [-95, -74, -66, -58, -39, -10, -5, 17, 31, 32, 37, 46, 60, 74, 94, 96, 97]\n",
      "After sorting: [-95, -74, -66, -58, -39, -10, -5, 17, 31, 32, 37, 46, 60, 74, 94, 96, 97]\n",
      "\n",
      "#86 Loop (passed: 86/100):\n",
      "Proper answer: [-94, -69, -65, 1, 23]\n",
      "After sorting: [-94, -69, -65, 1, 23]\n",
      "\n",
      "#87 Loop (passed: 87/100):\n",
      "Proper answer: [-86, -74, -73, -49, -42, -19, -16, -9, -8, 6, 52, 54, 82]\n",
      "After sorting: [-86, -74, -73, -49, -42, -19, -16, -9, -8, 6, 52, 54, 82]\n",
      "\n",
      "#88 Loop (passed: 88/100):\n",
      "Proper answer: [-99, -68, -65, -56, 10, 11, 35, 36, 50, 76]\n",
      "After sorting: [-99, -68, -65, -56, 10, 11, 35, 36, 50, 76]\n",
      "\n",
      "#89 Loop (passed: 89/100):\n",
      "Proper answer: [-98, -93, -85, -83, -82, -75, -46, 10, 19, 39, 40, 45, 51, 52, 55, 59, 64, 66, 93, 97]\n",
      "After sorting: [-98, -93, -85, -83, -82, -75, -46, 10, 19, 39, 40, 45, 51, 52, 55, 59, 64, 66, 93, 97]\n",
      "\n",
      "#90 Loop (passed: 90/100):\n",
      "Proper answer: [-75, -50, -49, -43, -41, -39, -16, -7, 4, 6, 13, 15, 25, 37]\n",
      "After sorting: [-75, -50, -49, -43, -41, -39, -16, -7, 4, 6, 13, 15, 25, 37]\n",
      "\n",
      "#91 Loop (passed: 91/100):\n",
      "Proper answer: [-89, -60, -52, -47, -22, -16, 13, 28, 48, 59, 88]\n",
      "After sorting: [-89, -60, -52, -47, -22, -16, 13, 28, 48, 59, 88]\n",
      "\n",
      "#92 Loop (passed: 92/100):\n",
      "Proper answer: [-88, -77, -66, -53, -48, -48, -8, 26, 32, 59, 95]\n",
      "After sorting: [-88, -77, -66, -53, -48, -48, -8, 26, 32, 59, 95]\n",
      "\n",
      "#93 Loop (passed: 93/100):\n",
      "Proper answer: [-97, -91, -76, -68, -64, -51, -51, -44, -39, -31, -19, -13, -11, -7, 0, 3, 11, 17, 57, 61, 68, 77, 87, 92]\n",
      "After sorting: [-97, -91, -76, -68, -64, -51, -51, -44, -39, -31, -19, -13, -11, -7, 0, 3, 11, 17, 57, 61, 68, 77, 87, 92]\n",
      "\n",
      "#94 Loop (passed: 94/100):\n",
      "Proper answer: [-99, -88, -53, -48, -45, -27, -26, -24, -19, -19, -17, -10, 7, 21, 30, 30, 32, 33, 48, 49, 70, 74, 89]\n",
      "After sorting: [-99, -88, -53, -48, -45, -27, -26, -24, -19, -19, -17, -10, 7, 21, 30, 30, 32, 33, 48, 49, 70, 74, 89]\n",
      "\n",
      "#95 Loop (passed: 95/100):\n",
      "Proper answer: [-79, -54, -50, -45, -15, -13, -2, 14, 15, 17, 26]\n",
      "After sorting: [-79, -54, -50, -45, -15, -13, -2, 14, 15, 17, 26]\n",
      "\n",
      "#96 Loop (passed: 96/100):\n",
      "Proper answer: [-98, -90, -57, -56, -53, -49, -29, -28, -13, 29, 40, 80]\n",
      "After sorting: [-98, -90, -57, -56, -53, -49, -29, -28, -13, 29, 40, 80]\n",
      "\n",
      "#97 Loop (passed: 97/100):\n",
      "Proper answer: [-100, -100, -81, -73, -61, -44, -38, -26, -22, -18, -10, -9, -2, 6, 26, 29, 36, 36, 43, 45, 46, 48, 53, 59, 75, 84, 86, 88]\n",
      "After sorting: [-100, -100, -81, -73, -61, -44, -38, -26, -22, -18, -10, -9, -2, 6, 26, 29, 36, 36, 43, 45, 46, 48, 53, 59, 75, 84, 86, 88]\n",
      "\n",
      "#98 Loop (passed: 98/100):\n",
      "Proper answer: [-96, -89, -79, -79, -67, -59, -39, -30, -10, -3, 3, 10, 12, 23, 25, 30, 33, 36, 40, 50, 61, 63, 80, 85, 88, 96]\n",
      "After sorting: [-96, -89, -79, -79, -67, -59, -39, -30, -10, -3, 3, 10, 12, 23, 25, 30, 33, 36, 40, 50, 61, 63, 80, 85, 88, 96]\n",
      "\n",
      "#99 Loop (passed: 99/100):\n",
      "Proper answer: [-95, -78, -63, -63, -55, -32, -28, -27, -11, -8, 0, 1, 5, 76, 95]\n",
      "After sorting: [-95, -78, -63, -63, -55, -32, -28, -27, -11, -8, 0, 1, 5, 76, 95]\n",
      "\n",
      "#100 Loop (passed: 100/100):\n",
      "Proper answer: [-88, -75, -73, -71, -71, -55, -43, -39, -32, -22, -5, 0, 3, 7, 18, 31, 43, 53, 54, 57, 59, 65, 67, 75, 78, 81, 88]\n",
      "After sorting: [-88, -75, -73, -71, -71, -55, -43, -39, -32, -22, -5, 0, 3, 7, 18, 31, 43, 53, 54, 57, 59, 65, 67, 75, 78, 81, 88]\n",
      "\n",
      "Total passed tests: 100/100\n",
      "A sorting algorithm is implemented correctly\n"
     ]
    }
   ],
   "source": [
    "test_sort(selection_sort, samples=100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### #4 (dodatkowo) c) sortowanie bąbelkowe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Poprzez zamianę wartości (działa tylko, gdy węzły przechowują pojedyncze wartości, np. liczby)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bubble_sort(ll):\n",
    "    if len(ll) < 2: return\n",
    "    \n",
    "    marker = ll.head\n",
    "    limit = None  # We use limit in order to speed up sorting (after each inner loop we are sure\n",
    "                  # that on the position that we finished is placed the currently greatest value)\n",
    "    while marker.next:\n",
    "        curr = ll.head\n",
    "        while curr.next is not limit:\n",
    "            if curr.next.val < curr.val:\n",
    "                curr.val, curr.next.val = curr.next.val, curr.val\n",
    "            curr = curr.next\n",
    "        limit = curr\n",
    "#         print(limit.val)\n",
    "        marker = marker.next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Przykładowy test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#1 Loop (passed: 1/100):\n",
      "Proper answer: [-92, -88, -76, -56, -54, -49, -40, -24, 0, 1, 8, 12, 35, 70, 91, 96, 100]\n",
      "After sorting: [-92, -88, -76, -56, -54, -49, -40, -24, 0, 1, 8, 12, 35, 70, 91, 96, 100]\n",
      "\n",
      "#2 Loop (passed: 2/100):\n",
      "Proper answer: [-97, -88, -86, -69, -69, -60, -58, -56, -47, -30, -17, -14, -13, -5, 2, 8, 13, 20, 42, 60, 65, 76, 85, 86, 87, 90, 90, 92, 98]\n",
      "After sorting: [-97, -88, -86, -69, -69, -60, -58, -56, -47, -30, -17, -14, -13, -5, 2, 8, 13, 20, 42, 60, 65, 76, 85, 86, 87, 90, 90, 92, 98]\n",
      "\n",
      "#3 Loop (passed: 3/100):\n",
      "Proper answer: [-92, -44, -4, -1, 50, 83, 89]\n",
      "After sorting: [-92, -44, -4, -1, 50, 83, 89]\n",
      "\n",
      "#4 Loop (passed: 4/100):\n",
      "Proper answer: [-77, -73, -70, -62, -60, -49, -33, -25, -19, -11, -2, 15, 15, 16, 18, 41, 44, 60, 61, 68, 68, 70, 89]\n",
      "After sorting: [-77, -73, -70, -62, -60, -49, -33, -25, -19, -11, -2, 15, 15, 16, 18, 41, 44, 60, 61, 68, 68, 70, 89]\n",
      "\n",
      "#5 Loop (passed: 5/100):\n",
      "Proper answer: [-89, -89, -58, -57, -7, 6, 17, 46, 60, 72, 72, 94]\n",
      "After sorting: [-89, -89, -58, -57, -7, 6, 17, 46, 60, 72, 72, 94]\n",
      "\n",
      "#6 Loop (passed: 6/100):\n",
      "Proper answer: [-70, -45, -41, -31, -22, -2, 8, 14, 29, 37, 58, 71, 86, 95]\n",
      "After sorting: [-70, -45, -41, -31, -22, -2, 8, 14, 29, 37, 58, 71, 86, 95]\n",
      "\n",
      "#7 Loop (passed: 7/100):\n",
      "Proper answer: [-96, -95, -90, -80, -79, -75, -55, -54, -50, -23, 0, 1, 2, 4, 6, 20, 60, 77, 80, 86, 89, 92]\n",
      "After sorting: [-96, -95, -90, -80, -79, -75, -55, -54, -50, -23, 0, 1, 2, 4, 6, 20, 60, 77, 80, 86, 89, 92]\n",
      "\n",
      "#8 Loop (passed: 8/100):\n",
      "Proper answer: [-68, -9, -4, -1, 13, 25, 41, 80]\n",
      "After sorting: [-68, -9, -4, -1, 13, 25, 41, 80]\n",
      "\n",
      "#9 Loop (passed: 9/100):\n",
      "Proper answer: [-82, -75, -71, -63, -55, -53, -50, -44, -42, -29, -24, -23, -22, -8, 11, 30, 42, 45, 48, 63, 75, 79]\n",
      "After sorting: [-82, -75, -71, -63, -55, -53, -50, -44, -42, -29, -24, -23, -22, -8, 11, 30, 42, 45, 48, 63, 75, 79]\n",
      "\n",
      "#10 Loop (passed: 10/100):\n",
      "Proper answer: [-96, -96, -74, -64, -56, -48, -42, -5, 12, 37, 47, 49, 54, 67, 72, 80]\n",
      "After sorting: [-96, -96, -74, -64, -56, -48, -42, -5, 12, 37, 47, 49, 54, 67, 72, 80]\n",
      "\n",
      "#11 Loop (passed: 11/100):\n",
      "Proper answer: [-92, -84, -79, -73, -65, -62, -58, -57, -51, -50, -38, -35, -27, 7, 38, 54, 61, 65, 67, 87, 91, 97]\n",
      "After sorting: [-92, -84, -79, -73, -65, -62, -58, -57, -51, -50, -38, -35, -27, 7, 38, 54, 61, 65, 67, 87, 91, 97]\n",
      "\n",
      "#12 Loop (passed: 12/100):\n",
      "Proper answer: [-68, -56, 15, 22, 28, 34, 38, 66, 82]\n",
      "After sorting: [-68, -56, 15, 22, 28, 34, 38, 66, 82]\n",
      "\n",
      "#13 Loop (passed: 13/100):\n",
      "Proper answer: [-98, -87, -85, -66, -52, -52, -49, -47, -42, -34, -31, -25, -24, -24, -17, -12, -9, -8, -2, 30, 33, 47, 51, 64, 64, 66, 76, 77, 79, 95]\n",
      "After sorting: [-98, -87, -85, -66, -52, -52, -49, -47, -42, -34, -31, -25, -24, -24, -17, -12, -9, -8, -2, 30, 33, 47, 51, 64, 64, 66, 76, 77, 79, 95]\n",
      "\n",
      "#14 Loop (passed: 14/100):\n",
      "Proper answer: [-84, -74, -72, -59, -47, -21, 8, 15, 20, 33, 42, 46, 65, 87, 91, 91]\n",
      "After sorting: [-84, -74, -72, -59, -47, -21, 8, 15, 20, 33, 42, 46, 65, 87, 91, 91]\n",
      "\n",
      "#15 Loop (passed: 15/100):\n",
      "Proper answer: [-99, -98, -94, -90, -74, -71, -66, -54, -51, -42, -35, -35, -21, -5, 5, 13, 49, 55, 58, 59, 60, 87, 90]\n",
      "After sorting: [-99, -98, -94, -90, -74, -71, -66, -54, -51, -42, -35, -35, -21, -5, 5, 13, 49, 55, 58, 59, 60, 87, 90]\n",
      "\n",
      "#16 Loop (passed: 16/100):\n",
      "Proper answer: [-98, -95, -90, -64, -60, -59, -36, -16, -14, 1, 3, 7, 9, 32, 36, 69, 70, 80, 83, 89, 91]\n",
      "After sorting: [-98, -95, -90, -64, -60, -59, -36, -16, -14, 1, 3, 7, 9, 32, 36, 69, 70, 80, 83, 89, 91]\n",
      "\n",
      "#17 Loop (passed: 17/100):\n",
      "Proper answer: [-93, -67, -1, 18, 81, 90]\n",
      "After sorting: [-93, -67, -1, 18, 81, 90]\n",
      "\n",
      "#18 Loop (passed: 18/100):\n",
      "Proper answer: [-87, -67, -59, -57, -50, -14, -4, 17, 18]\n",
      "After sorting: [-87, -67, -59, -57, -50, -14, -4, 17, 18]\n",
      "\n",
      "#19 Loop (passed: 19/100):\n",
      "Proper answer: [-89, -84, -79, -62, -54, -48, -42, -38, -26, -19, -17, -15, -12, -6, 4, 17, 45, 53, 55, 60, 66, 77, 92, 95, 100]\n",
      "After sorting: [-89, -84, -79, -62, -54, -48, -42, -38, -26, -19, -17, -15, -12, -6, 4, 17, 45, 53, 55, 60, 66, 77, 92, 95, 100]\n",
      "\n",
      "#20 Loop (passed: 20/100):\n",
      "Proper answer: [-99, -94, -93, -65, -58, -39, -35, -27, -25, -19, -17, -14, -1, 0, 12, 37, 38, 44, 60, 73, 81, 84, 84, 93, 93]\n",
      "After sorting: [-99, -94, -93, -65, -58, -39, -35, -27, -25, -19, -17, -14, -1, 0, 12, 37, 38, 44, 60, 73, 81, 84, 84, 93, 93]\n",
      "\n",
      "#21 Loop (passed: 21/100):\n",
      "Proper answer: [-98, -68, -68, -67, -57, -24, 15, 27, 44, 64, 64, 73]\n",
      "After sorting: [-98, -68, -68, -67, -57, -24, 15, 27, 44, 64, 64, 73]\n",
      "\n",
      "#22 Loop (passed: 22/100):\n",
      "Proper answer: [-95, -85, -84, -73, -63, -59, -37, -26, -3, 0, 1, 13, 18, 32, 35, 48, 60, 61, 74, 86, 87, 93]\n",
      "After sorting: [-95, -85, -84, -73, -63, -59, -37, -26, -3, 0, 1, 13, 18, 32, 35, 48, 60, 61, 74, 86, 87, 93]\n",
      "\n",
      "#23 Loop (passed: 23/100):\n",
      "Proper answer: [-100, -100, -94, -91, -88, -87, -70, -66, -39, -26, -24, -17, -17, -9, -3, -3, 0, 0, 21, 34, 34, 37, 50, 63, 72, 75, 93, 94]\n",
      "After sorting: [-100, -100, -94, -91, -88, -87, -70, -66, -39, -26, -24, -17, -17, -9, -3, -3, 0, 0, 21, 34, 34, 37, 50, 63, 72, 75, 93, 94]\n",
      "\n",
      "#24 Loop (passed: 24/100):\n",
      "Proper answer: [-100, -100, -76, -59, -53, -50, -43, -43, -37, -34, -11, -2, 9, 14, 17, 18, 40, 53, 81, 93, 96]\n",
      "After sorting: [-100, -100, -76, -59, -53, -50, -43, -43, -37, -34, -11, -2, 9, 14, 17, 18, 40, 53, 81, 93, 96]\n",
      "\n",
      "#25 Loop (passed: 25/100):\n",
      "Proper answer: [-86, -77, -74, -58, -43, -2, 13, 22, 23, 23, 52, 58, 74, 82, 85, 87, 95]\n",
      "After sorting: [-86, -77, -74, -58, -43, -2, 13, 22, 23, 23, 52, 58, 74, 82, 85, 87, 95]\n",
      "\n",
      "#26 Loop (passed: 26/100):\n",
      "Proper answer: [-93, -89, -84, -66, -66, -65, -57, -50, -49, -48, -32, -29, -27, -26, 10, 12, 13, 32, 46, 65, 77]\n",
      "After sorting: [-93, -89, -84, -66, -66, -65, -57, -50, -49, -48, -32, -29, -27, -26, 10, 12, 13, 32, 46, 65, 77]\n",
      "\n",
      "#27 Loop (passed: 27/100):\n",
      "Proper answer: [-66, -50, -29, -25, -7, 70, 95]\n",
      "After sorting: [-66, -50, -29, -25, -7, 70, 95]\n",
      "\n",
      "#28 Loop (passed: 28/100):\n",
      "Proper answer: [-91, -82, -71, -66, -64, -47, -42, -40, -38, -32, -27, -24, -22, -16, -6, 4, 5, 11, 45, 50, 66, 66, 69, 69, 71, 73, 96]\n",
      "After sorting: [-91, -82, -71, -66, -64, -47, -42, -40, -38, -32, -27, -24, -22, -16, -6, 4, 5, 11, 45, 50, 66, 66, 69, 69, 71, 73, 96]\n",
      "\n",
      "#29 Loop (passed: 29/100):\n",
      "Proper answer: [-89, -82, -75, -63, -50, -49, -41, -23, -18, -16, 18, 23, 38, 41, 42, 51, 55, 81, 93]\n",
      "After sorting: [-89, -82, -75, -63, -50, -49, -41, -23, -18, -16, 18, 23, 38, 41, 42, 51, 55, 81, 93]\n",
      "\n",
      "#30 Loop (passed: 30/100):\n",
      "Proper answer: [-28, 1, 26, 27, 36, 38, 99]\n",
      "After sorting: [-28, 1, 26, 27, 36, 38, 99]\n",
      "\n",
      "#31 Loop (passed: 31/100):\n",
      "Proper answer: [-87, -78, -75, -62, -53, -43, -38, -38, -34, -31, -17, -4, 1, 20, 25, 36, 46, 48, 52, 57, 62, 77, 81, 84, 88, 93]\n",
      "After sorting: [-87, -78, -75, -62, -53, -43, -38, -38, -34, -31, -17, -4, 1, 20, 25, 36, 46, 48, 52, 57, 62, 77, 81, 84, 88, 93]\n",
      "\n",
      "#32 Loop (passed: 32/100):\n",
      "Proper answer: [-92, -73, -66, -64, -61, -60, -55, -32, -27, -25, -19, -3, 16, 18, 28, 37, 41, 41, 41, 68, 78, 86, 89]\n",
      "After sorting: [-92, -73, -66, -64, -61, -60, -55, -32, -27, -25, -19, -3, 16, 18, 28, 37, 41, 41, 41, 68, 78, 86, 89]\n",
      "\n",
      "#33 Loop (passed: 33/100):\n",
      "Proper answer: [-96, -84, -69, -63, 28, 29, 53, 68]\n",
      "After sorting: [-96, -84, -69, -63, 28, 29, 53, 68]\n",
      "\n",
      "#34 Loop (passed: 34/100):\n",
      "Proper answer: [-92, -91, -87, -76, -72, -69, -68, -56, -51, -20, -18, 4, 10, 11, 20, 41, 54, 74, 85]\n",
      "After sorting: [-92, -91, -87, -76, -72, -69, -68, -56, -51, -20, -18, 4, 10, 11, 20, 41, 54, 74, 85]\n",
      "\n",
      "#35 Loop (passed: 35/100):\n",
      "Proper answer: [-88, -80, -71, -40, -38, -36, -34, -27, -18, -17, -16, -14, -13, -10, -5, 14, 18, 21, 24, 26, 26, 57, 71, 73, 77, 89, 90, 94, 94, 95]\n",
      "After sorting: [-88, -80, -71, -40, -38, -36, -34, -27, -18, -17, -16, -14, -13, -10, -5, 14, 18, 21, 24, 26, 26, 57, 71, 73, 77, 89, 90, 94, 94, 95]\n",
      "\n",
      "#36 Loop (passed: 36/100):\n",
      "Proper answer: [-98, -81, -57, -53, -52, -49, -46, -45, -19, -6, -5, 10, 17, 19, 19, 23, 26, 34, 46, 46, 53, 53, 64, 65, 71, 77, 79, 90, 98]\n",
      "After sorting: [-98, -81, -57, -53, -52, -49, -46, -45, -19, -6, -5, 10, 17, 19, 19, 23, 26, 34, 46, 46, 53, 53, 64, 65, 71, 77, 79, 90, 98]\n",
      "\n",
      "#37 Loop (passed: 37/100):\n",
      "Proper answer: [-62, -59, -57, -30, -23, -6, 43, 56]\n",
      "After sorting: [-62, -59, -57, -30, -23, -6, 43, 56]\n",
      "\n",
      "#38 Loop (passed: 38/100):\n",
      "Proper answer: [-65, -51, -34, -30, 6, 21, 24, 41, 49, 56, 63, 66, 74, 78, 86, 93, 100]\n",
      "After sorting: [-65, -51, -34, -30, 6, 21, 24, 41, 49, 56, 63, 66, 74, 78, 86, 93, 100]\n",
      "\n",
      "#39 Loop (passed: 39/100):\n",
      "Proper answer: [-80, -51, -38, -34, 7, 23, 56, 74, 76, 84, 87, 93, 97, 99]\n",
      "After sorting: [-80, -51, -38, -34, 7, 23, 56, 74, 76, 84, 87, 93, 97, 99]\n",
      "\n",
      "#40 Loop (passed: 40/100):\n",
      "Proper answer: [-100, -85, -63, -39, -35, -17, 21, 37, 49, 68, 83]\n",
      "After sorting: [-100, -85, -63, -39, -35, -17, 21, 37, 49, 68, 83]\n",
      "\n",
      "#41 Loop (passed: 41/100):\n",
      "Proper answer: [-94, -81, -77, -64, -62, -53, -21, -20, -20, -5, -3, 7, 33, 49, 55, 63, 68, 71, 75, 76, 80, 84, 94]\n",
      "After sorting: [-94, -81, -77, -64, -62, -53, -21, -20, -20, -5, -3, 7, 33, 49, 55, 63, 68, 71, 75, 76, 80, 84, 94]\n",
      "\n",
      "#42 Loop (passed: 42/100):\n",
      "Proper answer: [-99, -99, -85, -83, -80, -74, -58, -40, -37, -33, -26, -23, -21, -19, -9, 2, 24, 30, 34, 36, 39, 40, 43, 45, 76, 90]\n",
      "After sorting: [-99, -99, -85, -83, -80, -74, -58, -40, -37, -33, -26, -23, -21, -19, -9, 2, 24, 30, 34, 36, 39, 40, 43, 45, 76, 90]\n",
      "\n",
      "#43 Loop (passed: 43/100):\n",
      "Proper answer: [-98, -94, -88, -87, -74, -65, -54, -47, -46, -44, -43, -36, -29, -21, -10, -7, 0, 4, 25, 55, 68, 71, 75, 75, 76, 76, 77, 85, 97]\n",
      "After sorting: [-98, -94, -88, -87, -74, -65, -54, -47, -46, -44, -43, -36, -29, -21, -10, -7, 0, 4, 25, 55, 68, 71, 75, 75, 76, 76, 77, 85, 97]\n",
      "\n",
      "#44 Loop (passed: 44/100):\n",
      "Proper answer: [-100, -65, -61, -59, -56, -51, -51, -43, -35, -25, -11, -3, -2, 6, 18, 26, 45, 49, 69, 75]\n",
      "After sorting: [-100, -65, -61, -59, -56, -51, -51, -43, -35, -25, -11, -3, -2, 6, 18, 26, 45, 49, 69, 75]\n",
      "\n",
      "#45 Loop (passed: 45/100):\n",
      "Proper answer: [-94, -84, -76, -61, -57, -50, -3, 27, 30, 61, 81, 93]\n",
      "After sorting: [-94, -84, -76, -61, -57, -50, -3, 27, 30, 61, 81, 93]\n",
      "\n",
      "#46 Loop (passed: 46/100):\n",
      "Proper answer: [-79, -74, -62, -56, -44, -43, 58, 69, 80, 92]\n",
      "After sorting: [-79, -74, -62, -56, -44, -43, 58, 69, 80, 92]\n",
      "\n",
      "#47 Loop (passed: 47/100):\n",
      "Proper answer: [-95, -94, -81, -24, -1, 54, 56, 71, 84]\n",
      "After sorting: [-95, -94, -81, -24, -1, 54, 56, 71, 84]\n",
      "\n",
      "#48 Loop (passed: 48/100):\n",
      "Proper answer: [-99, -89, -68, -67, -47, -44, -38, -37, -35, -29, -20, -8, 16, 19, 24, 34, 39, 41, 64, 65, 82, 82, 85]\n",
      "After sorting: [-99, -89, -68, -67, -47, -44, -38, -37, -35, -29, -20, -8, 16, 19, 24, 34, 39, 41, 64, 65, 82, 82, 85]\n",
      "\n",
      "#49 Loop (passed: 49/100):\n",
      "Proper answer: [-67, -63, -62, -37, -29, -1, 7, 35, 37]\n",
      "After sorting: [-67, -63, -62, -37, -29, -1, 7, 35, 37]\n",
      "\n",
      "#50 Loop (passed: 50/100):\n",
      "Proper answer: [-97, -72, -71, -60, -13, 5, 12, 16, 63, 91, 94, 96]\n",
      "After sorting: [-97, -72, -71, -60, -13, 5, 12, 16, 63, 91, 94, 96]\n",
      "\n",
      "#51 Loop (passed: 51/100):\n",
      "Proper answer: [-99, -92, -68, -45, -38, -23, 0, 5, 21, 39, 50, 74, 74, 80, 82]\n",
      "After sorting: [-99, -92, -68, -45, -38, -23, 0, 5, 21, 39, 50, 74, 74, 80, 82]\n",
      "\n",
      "#52 Loop (passed: 52/100):\n",
      "Proper answer: [-81, -80, -65, -64, -20, 42, 46]\n",
      "After sorting: [-81, -80, -65, -64, -20, 42, 46]\n",
      "\n",
      "#53 Loop (passed: 53/100):\n",
      "Proper answer: [-99, -91, -90, -59, -50, -37, -25, -16, -15, 2, 50, 55, 55, 67, 75]\n",
      "After sorting: [-99, -91, -90, -59, -50, -37, -25, -16, -15, 2, 50, 55, 55, 67, 75]\n",
      "\n",
      "#54 Loop (passed: 54/100):\n",
      "Proper answer: [-96, -89, -83, -71, -66, -66, -55, -55, -49, -48, -43, -37, -36, -31, -28, -27, -21, 11, 28, 49, 70, 93, 93, 98, 100]\n",
      "After sorting: [-96, -89, -83, -71, -66, -66, -55, -55, -49, -48, -43, -37, -36, -31, -28, -27, -21, 11, 28, 49, 70, 93, 93, 98, 100]\n",
      "\n",
      "#55 Loop (passed: 55/100):\n",
      "Proper answer: [-97, -95, -92, -86, -82, -73, -72, -64, -61, -58, -58, -46, -38, -20, -19, -6, -6, -1, 21, 31, 37, 41, 43, 82, 100]\n",
      "After sorting: [-97, -95, -92, -86, -82, -73, -72, -64, -61, -58, -58, -46, -38, -20, -19, -6, -6, -1, 21, 31, 37, 41, 43, 82, 100]\n",
      "\n",
      "#56 Loop (passed: 56/100):\n",
      "Proper answer: [-77, -64, 3, 72, 94, 98]\n",
      "After sorting: [-77, -64, 3, 72, 94, 98]\n",
      "\n",
      "#57 Loop (passed: 57/100):\n",
      "Proper answer: [-96, -83, -77, -68, -59, -35, -23, -14, -8, -4, 11, 20, 27, 34, 48, 65, 83]\n",
      "After sorting: [-96, -83, -77, -68, -59, -35, -23, -14, -8, -4, 11, 20, 27, 34, 48, 65, 83]\n",
      "\n",
      "#58 Loop (passed: 58/100):\n",
      "Proper answer: [-54, -19, -3, 9, 23, 27]\n",
      "After sorting: [-54, -19, -3, 9, 23, 27]\n",
      "\n",
      "#59 Loop (passed: 59/100):\n",
      "Proper answer: [-100, -87, -68, -61, -44, -38, -37, -32, -28, -1, 1, 10, 37, 42, 47, 55, 59, 62, 93]\n",
      "After sorting: [-100, -87, -68, -61, -44, -38, -37, -32, -28, -1, 1, 10, 37, 42, 47, 55, 59, 62, 93]\n",
      "\n",
      "#60 Loop (passed: 60/100):\n",
      "Proper answer: [-97, -89, -84, -77, -51, -51, -38, 0, 17, 18, 40, 42, 67, 92, 96]\n",
      "After sorting: [-97, -89, -84, -77, -51, -51, -38, 0, 17, 18, 40, 42, 67, 92, 96]\n",
      "\n",
      "#61 Loop (passed: 61/100):\n",
      "Proper answer: [-98, -92, -65, -59, -59, -49, -41, -32, -2, 0, 14, 25, 30, 38, 53, 88, 95, 95]\n",
      "After sorting: [-98, -92, -65, -59, -59, -49, -41, -32, -2, 0, 14, 25, 30, 38, 53, 88, 95, 95]\n",
      "\n",
      "#62 Loop (passed: 62/100):\n",
      "Proper answer: [-49, -33, -10, -3, 8, 41, 47, 53, 66, 82]\n",
      "After sorting: [-49, -33, -10, -3, 8, 41, 47, 53, 66, 82]\n",
      "\n",
      "#63 Loop (passed: 63/100):\n",
      "Proper answer: [-93, 8, 72, 72, 75, 94]\n",
      "After sorting: [-93, 8, 72, 72, 75, 94]\n",
      "\n",
      "#64 Loop (passed: 64/100):\n",
      "Proper answer: [-100, -96, -96, -94, -92, -89, -69, -64, -58, -49, -47, -26, -13, -13, -11, -10, -7, 2, 5, 19, 30, 37, 37, 41, 43, 62, 73, 85, 90]\n",
      "After sorting: [-100, -96, -96, -94, -92, -89, -69, -64, -58, -49, -47, -26, -13, -13, -11, -10, -7, 2, 5, 19, 30, 37, 37, 41, 43, 62, 73, 85, 90]\n",
      "\n",
      "#65 Loop (passed: 65/100):\n",
      "Proper answer: [-97, -29, -29, -25, -16, -11, 3, 8, 68, 74, 94, 96, 99]\n",
      "After sorting: [-97, -29, -29, -25, -16, -11, 3, 8, 68, 74, 94, 96, 99]\n",
      "\n",
      "#66 Loop (passed: 66/100):\n",
      "Proper answer: [-99, -92, -85, -82, -63, -41, 5, 16, 32, 34, 39, 65]\n",
      "After sorting: [-99, -92, -85, -82, -63, -41, 5, 16, 32, 34, 39, 65]\n",
      "\n",
      "#67 Loop (passed: 67/100):\n",
      "Proper answer: [-96, -93, -91, -86, -82, -72, -58, -46, -43, -42, -22, -21, 9, 15, 18, 26, 30, 31, 75, 80, 83, 85, 91, 94, 100]\n",
      "After sorting: [-96, -93, -91, -86, -82, -72, -58, -46, -43, -42, -22, -21, 9, 15, 18, 26, 30, 31, 75, 80, 83, 85, 91, 94, 100]\n",
      "\n",
      "#68 Loop (passed: 68/100):\n",
      "Proper answer: [-69, -34, -29, 43, 45, 50, 51, 75]\n",
      "After sorting: [-69, -34, -29, 43, 45, 50, 51, 75]\n",
      "\n",
      "#69 Loop (passed: 69/100):\n",
      "Proper answer: [-95, -82, -55, -51, -27, -25, -13, 7, 58, 71, 79, 95]\n",
      "After sorting: [-95, -82, -55, -51, -27, -25, -13, 7, 58, 71, 79, 95]\n",
      "\n",
      "#70 Loop (passed: 70/100):\n",
      "Proper answer: [-99, -75, -62, -53, -52, 15, 30, 36, 46, 48, 82, 86]\n",
      "After sorting: [-99, -75, -62, -53, -52, 15, 30, 36, 46, 48, 82, 86]\n",
      "\n",
      "#71 Loop (passed: 71/100):\n",
      "Proper answer: [-68, -41, -8, 7, 17, 31]\n",
      "After sorting: [-68, -41, -8, 7, 17, 31]\n",
      "\n",
      "#72 Loop (passed: 72/100):\n",
      "Proper answer: [-99, -94, -79, -52, -49, -32, -23, -19, 17, 22, 23, 26, 34, 45, 53, 57, 68, 71, 78, 84]\n",
      "After sorting: [-99, -94, -79, -52, -49, -32, -23, -19, 17, 22, 23, 26, 34, 45, 53, 57, 68, 71, 78, 84]\n",
      "\n",
      "#73 Loop (passed: 73/100):\n",
      "Proper answer: [-92, -86, -84, -80, -52, -51, -49, -46, -42, -40, -36, -10, -2, 0, 1, 19, 34, 37, 42, 42, 56, 78, 89, 89, 94, 96]\n",
      "After sorting: [-92, -86, -84, -80, -52, -51, -49, -46, -42, -40, -36, -10, -2, 0, 1, 19, 34, 37, 42, 42, 56, 78, 89, 89, 94, 96]\n",
      "\n",
      "#74 Loop (passed: 74/100):\n",
      "Proper answer: [-91, -91, -89, -79, -73, -54, -43, -41, -8, 0, 1, 2, 5, 17, 18, 37, 41, 55, 69, 77, 77]\n",
      "After sorting: [-91, -91, -89, -79, -73, -54, -43, -41, -8, 0, 1, 2, 5, 17, 18, 37, 41, 55, 69, 77, 77]\n",
      "\n",
      "#75 Loop (passed: 75/100):\n",
      "Proper answer: [-99, -86, -79, -65, -60, -55, -53, -48, -41, -41, -34, -29, -25, 32, 51, 51, 59, 60, 62, 66, 86, 87, 87]\n",
      "After sorting: [-99, -86, -79, -65, -60, -55, -53, -48, -41, -41, -34, -29, -25, 32, 51, 51, 59, 60, 62, 66, 86, 87, 87]\n",
      "\n",
      "#76 Loop (passed: 76/100):\n",
      "Proper answer: [-79, -76, -72, -54, -53, -23, -19, 1, 4, 12, 20, 38, 46, 53, 55, 59, 59, 60, 63, 64, 65, 67, 67, 77, 81, 93, 96, 100]\n",
      "After sorting: [-79, -76, -72, -54, -53, -23, -19, 1, 4, 12, 20, 38, 46, 53, 55, 59, 59, 60, 63, 64, 65, 67, 67, 77, 81, 93, 96, 100]\n",
      "\n",
      "#77 Loop (passed: 77/100):\n",
      "Proper answer: [-82, -75, 4, 15, 18, 32, 50, 56, 97]\n",
      "After sorting: [-82, -75, 4, 15, 18, 32, 50, 56, 97]\n",
      "\n",
      "#78 Loop (passed: 78/100):\n",
      "Proper answer: [-94, -81, -38, -22, 0, 13, 17, 23, 52, 78]\n",
      "After sorting: [-94, -81, -38, -22, 0, 13, 17, 23, 52, 78]\n",
      "\n",
      "#79 Loop (passed: 79/100):\n",
      "Proper answer: [-95, -84, -79, -57, -30, 15, 16, 26, 48, 97]\n",
      "After sorting: [-95, -84, -79, -57, -30, 15, 16, 26, 48, 97]\n",
      "\n",
      "#80 Loop (passed: 80/100):\n",
      "Proper answer: [-89, -88, -82, -82, -53, -47, -44, -39, -29, -6, 3, 6, 7, 8, 13, 21, 48, 56, 60, 61, 65, 94, 94]\n",
      "After sorting: [-89, -88, -82, -82, -53, -47, -44, -39, -29, -6, 3, 6, 7, 8, 13, 21, 48, 56, 60, 61, 65, 94, 94]\n",
      "\n",
      "#81 Loop (passed: 81/100):\n",
      "Proper answer: [-100, -80, 7, 22, 24, 65, 83]\n",
      "After sorting: [-100, -80, 7, 22, 24, 65, 83]\n",
      "\n",
      "#82 Loop (passed: 82/100):\n",
      "Proper answer: [-93, -89, -66, -36, -36, -17, -2, 5, 15, 31, 34, 38, 39, 47, 51, 60, 67, 67, 70, 86, 94, 95, 99]\n",
      "After sorting: [-93, -89, -66, -36, -36, -17, -2, 5, 15, 31, 34, 38, 39, 47, 51, 60, 67, 67, 70, 86, 94, 95, 99]\n",
      "\n",
      "#83 Loop (passed: 83/100):\n",
      "Proper answer: [-96, -67, -43, 73, 78, 89, 97]\n",
      "After sorting: [-96, -67, -43, 73, 78, 89, 97]\n",
      "\n",
      "#84 Loop (passed: 84/100):\n",
      "Proper answer: [-98, -98, -91, -89, -74, -48, -42, -35, -35, -15, 3, 21, 27, 35, 38, 41, 41, 45, 58, 66, 76, 89, 100]\n",
      "After sorting: [-98, -98, -91, -89, -74, -48, -42, -35, -35, -15, 3, 21, 27, 35, 38, 41, 41, 45, 58, 66, 76, 89, 100]\n",
      "\n",
      "#85 Loop (passed: 85/100):\n",
      "Proper answer: [-97, -89, -85, -64, -54, -43, -40, -37, -16, -15, -8, 5, 11, 29, 31, 52, 54, 65, 74, 74, 79, 85, 96, 99]\n",
      "After sorting: [-97, -89, -85, -64, -54, -43, -40, -37, -16, -15, -8, 5, 11, 29, 31, 52, 54, 65, 74, 74, 79, 85, 96, 99]\n",
      "\n",
      "#86 Loop (passed: 86/100):\n",
      "Proper answer: [-96, -87, -61, -30, -28, -24, -24, -8, 12, 36, 51, 71, 83, 92, 95, 95]\n",
      "After sorting: [-96, -87, -61, -30, -28, -24, -24, -8, 12, 36, 51, 71, 83, 92, 95, 95]\n",
      "\n",
      "#87 Loop (passed: 87/100):\n",
      "Proper answer: [-44, -11, 22, 59, 98]\n",
      "After sorting: [-44, -11, 22, 59, 98]\n",
      "\n",
      "#88 Loop (passed: 88/100):\n",
      "Proper answer: [-72, -55, -49, -21, -9, -2, -2, 13, 18, 24, 35, 51, 60, 74, 96]\n",
      "After sorting: [-72, -55, -49, -21, -9, -2, -2, 13, 18, 24, 35, 51, 60, 74, 96]\n",
      "\n",
      "#89 Loop (passed: 89/100):\n",
      "Proper answer: [-95, -86, -81, -81, -80, -72, -72, -56, -51, -38, -37, -3, 3, 25, 35, 35, 36, 41, 45, 46, 48, 55, 57, 75, 77, 77]\n",
      "After sorting: [-95, -86, -81, -81, -80, -72, -72, -56, -51, -38, -37, -3, 3, 25, 35, 35, 36, 41, 45, 46, 48, 55, 57, 75, 77, 77]\n",
      "\n",
      "#90 Loop (passed: 90/100):\n",
      "Proper answer: [-100, -99, -94, -88, -86, -68, -58, -44, -32, -20, -18, -17, -2, 16, 17, 26, 26, 28, 39, 51, 60, 61, 65, 85, 99]\n",
      "After sorting: [-100, -99, -94, -88, -86, -68, -58, -44, -32, -20, -18, -17, -2, 16, 17, 26, 26, 28, 39, 51, 60, 61, 65, 85, 99]\n",
      "\n",
      "#91 Loop (passed: 91/100):\n",
      "Proper answer: [-89, -66, -58, -55, -51, -50, -32, -9, -8, -5, -5, -5, -2, 29, 57, 69, 92]\n",
      "After sorting: [-89, -66, -58, -55, -51, -50, -32, -9, -8, -5, -5, -5, -2, 29, 57, 69, 92]\n",
      "\n",
      "#92 Loop (passed: 92/100):\n",
      "Proper answer: [-88, -7, 11, 22, 25, 42, 44, 46, 76, 88, 88]\n",
      "After sorting: [-88, -7, 11, 22, 25, 42, 44, 46, 76, 88, 88]\n",
      "\n",
      "#93 Loop (passed: 93/100):\n",
      "Proper answer: [-99, -80, -78, -62, -60, -56, -52, -47, -39, -12, -1, 10, 32, 52, 54, 54, 63, 72, 77, 78, 84, 87, 92, 95, 98]\n",
      "After sorting: [-99, -80, -78, -62, -60, -56, -52, -47, -39, -12, -1, 10, 32, 52, 54, 54, 63, 72, 77, 78, 84, 87, 92, 95, 98]\n",
      "\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#94 Loop (passed: 94/100):\n",
      "Proper answer: [-99, -96, -88, -68, -47, -40, -32, 54, 63, 65, 90]\n",
      "After sorting: [-99, -96, -88, -68, -47, -40, -32, 54, 63, 65, 90]\n",
      "\n",
      "#95 Loop (passed: 95/100):\n",
      "Proper answer: [-96, -87, -81, -80, -68, -57, -53, -44, -43, -11, -10, -7, 4, 15, 36, 38, 47, 52, 54, 60, 71, 83, 94]\n",
      "After sorting: [-96, -87, -81, -80, -68, -57, -53, -44, -43, -11, -10, -7, 4, 15, 36, 38, 47, 52, 54, 60, 71, 83, 94]\n",
      "\n",
      "#96 Loop (passed: 96/100):\n",
      "Proper answer: [-41, -33, -26, 43, 52, 85]\n",
      "After sorting: [-41, -33, -26, 43, 52, 85]\n",
      "\n",
      "#97 Loop (passed: 97/100):\n",
      "Proper answer: [-62, -41, -36, -27, -24, -13, -9, -8, -8, -3, 6, 27, 38, 84, 100]\n",
      "After sorting: [-62, -41, -36, -27, -24, -13, -9, -8, -8, -3, 6, 27, 38, 84, 100]\n",
      "\n",
      "#98 Loop (passed: 98/100):\n",
      "Proper answer: [-89, -88, -73, -52, -47, -42, -41, -29, -24, -20, -18, -13, -1, 36, 36, 68, 88, 98]\n",
      "After sorting: [-89, -88, -73, -52, -47, -42, -41, -29, -24, -20, -18, -13, -1, 36, 36, 68, 88, 98]\n",
      "\n",
      "#99 Loop (passed: 99/100):\n",
      "Proper answer: [-100, -61, -51, -41, -37, -29, -28, -4, -1, 7, 22, 26, 29, 33, 56, 63, 83, 86]\n",
      "After sorting: [-100, -61, -51, -41, -37, -29, -28, -4, -1, 7, 22, 26, 29, 33, 56, 63, 83, 86]\n",
      "\n",
      "#100 Loop (passed: 100/100):\n",
      "Proper answer: [-100, -82, -11, -8, -5, 66, 75, 98]\n",
      "After sorting: [-100, -82, -11, -8, -5, 66, 75, 98]\n",
      "\n",
      "Total passed tests: 100/100\n",
      "A sorting algorithm is implemented correctly\n"
     ]
    }
   ],
   "source": [
    "test_sort(bubble_sort, samples=100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Poprzez modyfikację wskaźników (bardziej ogólne - węzły mogą przechowywać dowolne dane - sortowanie według klucza (wartości) przestawia całe węzły, a nie zamienia danych, jak to powyżej)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def swap_nodes(first, second, third):\n",
    "    second.next = third.next\n",
    "    third.next = second\n",
    "    first.next = third\n",
    "\n",
    "\n",
    "def bubble_sort(ll):\n",
    "    if len(ll) < 2: return\n",
    "    # Store a loops count of an outer loop and a limit node\n",
    "    loops = len(ll) - 1\n",
    "    limit = None\n",
    "    # Add a sentinel node\n",
    "    ll.prepend(None)\n",
    "    # Loop over a Linked List and modify pointers (if necessary) in order to swap nodes\n",
    "    for _ in range(loops):\n",
    "        prev = ll.head\n",
    "        while prev.next.next is not limit:\n",
    "            if prev.next.next.val < prev.next.val:\n",
    "                swap_nodes(prev, prev.next, prev.next.next)\n",
    "            prev = prev.next\n",
    "        limit = prev.next\n",
    "#         print(limit.val)\n",
    "    # Remove a sentinel node\n",
    "    ll.popleft()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Przykładowy test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#1 Loop (passed: 1/100):\n",
      "Proper answer: [-80, -68, -44, -11, -11, 16, 25, 27, 40, 49, 56, 69]\n",
      "After sorting: [-80, -68, -44, -11, -11, 16, 25, 27, 40, 49, 56, 69]\n",
      "\n",
      "#2 Loop (passed: 2/100):\n",
      "Proper answer: [-81, -77, -64, -60, -21, 14, 31, 49, 56]\n",
      "After sorting: [-81, -77, -64, -60, -21, 14, 31, 49, 56]\n",
      "\n",
      "#3 Loop (passed: 3/100):\n",
      "Proper answer: [-98, -95, -89, -88, -83, -68, -63, -59, -29, -23, -2, 9, 15, 29, 48, 49, 54, 55, 57, 60, 60, 67, 69, 69, 82, 86, 95]\n",
      "After sorting: [-98, -95, -89, -88, -83, -68, -63, -59, -29, -23, -2, 9, 15, 29, 48, 49, 54, 55, 57, 60, 60, 67, 69, 69, 82, 86, 95]\n",
      "\n",
      "#4 Loop (passed: 4/100):\n",
      "Proper answer: [-89, -85, -79, -77, -75, -67, -59, -53, -51, -37, -33, -20, -15, -12, -2, -1, 10, 14, 14, 32, 38, 39, 48, 50, 53, 67, 68, 73, 78, 100]\n",
      "After sorting: [-89, -85, -79, -77, -75, -67, -59, -53, -51, -37, -33, -20, -15, -12, -2, -1, 10, 14, 14, 32, 38, 39, 48, 50, 53, 67, 68, 73, 78, 100]\n",
      "\n",
      "#5 Loop (passed: 5/100):\n",
      "Proper answer: [-71, -55, -51, -44, -23, -3, 8, 23, 47]\n",
      "After sorting: [-71, -55, -51, -44, -23, -3, 8, 23, 47]\n",
      "\n",
      "#6 Loop (passed: 6/100):\n",
      "Proper answer: [-87, -86, -79, -74, -70, -58, -57, -50, -45, -44, -41, -38, -26, -25, -21, -14, -12, 36, 38, 49, 52, 71, 71, 78, 88, 89, 91, 92]\n",
      "After sorting: [-87, -86, -79, -74, -70, -58, -57, -50, -45, -44, -41, -38, -26, -25, -21, -14, -12, 36, 38, 49, 52, 71, 71, 78, 88, 89, 91, 92]\n",
      "\n",
      "#7 Loop (passed: 7/100):\n",
      "Proper answer: [-100, -96, -94, -64, -46, -26, -23, -23, 12, 16, 20, 23, 25, 25, 67, 71, 90]\n",
      "After sorting: [-100, -96, -94, -64, -46, -26, -23, -23, 12, 16, 20, 23, 25, 25, 67, 71, 90]\n",
      "\n",
      "#8 Loop (passed: 8/100):\n",
      "Proper answer: [-91, -68, -62, -51, -23, 18, 55, 60, 65, 67]\n",
      "After sorting: [-91, -68, -62, -51, -23, 18, 55, 60, 65, 67]\n",
      "\n",
      "#9 Loop (passed: 9/100):\n",
      "Proper answer: [-86, -86, -65, -58, -58, -57, -23, -4, 13, 20, 37, 45, 54, 60, 63, 76]\n",
      "After sorting: [-86, -86, -65, -58, -58, -57, -23, -4, 13, 20, 37, 45, 54, 60, 63, 76]\n",
      "\n",
      "#10 Loop (passed: 10/100):\n",
      "Proper answer: [-96, -91, -90, -80, -53, -32, -25, -19, -17, -13, 0, 3, 31, 38, 51, 56, 72, 88, 90]\n",
      "After sorting: [-96, -91, -90, -80, -53, -32, -25, -19, -17, -13, 0, 3, 31, 38, 51, 56, 72, 88, 90]\n",
      "\n",
      "#11 Loop (passed: 11/100):\n",
      "Proper answer: [-99, -98, -92, -86, -83, -79, -74, -48, -39, -16, -16, -14, 4, 14, 25, 38, 38, 44, 57, 66, 96]\n",
      "After sorting: [-99, -98, -92, -86, -83, -79, -74, -48, -39, -16, -16, -14, 4, 14, 25, 38, 38, 44, 57, 66, 96]\n",
      "\n",
      "#12 Loop (passed: 12/100):\n",
      "Proper answer: [-93, -86, -65, -51, -30, -17, -5, -3, 0, 8, 16, 33, 53, 53, 56, 76]\n",
      "After sorting: [-93, -86, -65, -51, -30, -17, -5, -3, 0, 8, 16, 33, 53, 53, 56, 76]\n",
      "\n",
      "#13 Loop (passed: 13/100):\n",
      "Proper answer: [-92, -87, -81, -75, -75, -58, -53, -51, -39, -39, -36, -34, -33, -28, -3, 0, 4, 12, 23, 48, 66, 68, 91, 92]\n",
      "After sorting: [-92, -87, -81, -75, -75, -58, -53, -51, -39, -39, -36, -34, -33, -28, -3, 0, 4, 12, 23, 48, 66, 68, 91, 92]\n",
      "\n",
      "#14 Loop (passed: 14/100):\n",
      "Proper answer: [-73, -71, -50, -37, -7, -1, 13, 47, 57, 72, 73, 77, 81, 86, 87, 94, 97]\n",
      "After sorting: [-73, -71, -50, -37, -7, -1, 13, 47, 57, 72, 73, 77, 81, 86, 87, 94, 97]\n",
      "\n",
      "#15 Loop (passed: 15/100):\n",
      "Proper answer: [-62, -16, 5, 5, 5, 29, 47, 58, 67, 81, 89]\n",
      "After sorting: [-62, -16, 5, 5, 5, 29, 47, 58, 67, 81, 89]\n",
      "\n",
      "#16 Loop (passed: 16/100):\n",
      "Proper answer: [-93, -86, -64, -54, -40, -39, -11, -8, 32, 38, 52, 68, 73, 79, 92]\n",
      "After sorting: [-93, -86, -64, -54, -40, -39, -11, -8, 32, 38, 52, 68, 73, 79, 92]\n",
      "\n",
      "#17 Loop (passed: 17/100):\n",
      "Proper answer: [-91, -53, -18, -11, 7, 7, 13, 27, 41, 60, 83]\n",
      "After sorting: [-91, -53, -18, -11, 7, 7, 13, 27, 41, 60, 83]\n",
      "\n",
      "#18 Loop (passed: 18/100):\n",
      "Proper answer: [-85, -43, 26, 31, 42, 46, 69, 76]\n",
      "After sorting: [-85, -43, 26, 31, 42, 46, 69, 76]\n",
      "\n",
      "#19 Loop (passed: 19/100):\n",
      "Proper answer: [-93, -86, -80, -68, -65, -61, -60, -60, -52, -50, -37, -29, -27, -18, -15, -9, 2, 8, 8, 10, 14, 38, 50, 50, 52, 52, 54, 57, 65, 78]\n",
      "After sorting: [-93, -86, -80, -68, -65, -61, -60, -60, -52, -50, -37, -29, -27, -18, -15, -9, 2, 8, 8, 10, 14, 38, 50, 50, 52, 52, 54, 57, 65, 78]\n",
      "\n",
      "#20 Loop (passed: 20/100):\n",
      "Proper answer: [-98, -82, -80, -48, -31, -26, -9, 25, 26, 33, 45, 49, 60, 65, 73, 82, 85, 91, 100]\n",
      "After sorting: [-98, -82, -80, -48, -31, -26, -9, 25, 26, 33, 45, 49, 60, 65, 73, 82, 85, 91, 100]\n",
      "\n",
      "#21 Loop (passed: 21/100):\n",
      "Proper answer: [-100, -97, -94, -81, -62, -61, -47, -44, -35, -30, -27, 32, 83]\n",
      "After sorting: [-100, -97, -94, -81, -62, -61, -47, -44, -35, -30, -27, 32, 83]\n",
      "\n",
      "#22 Loop (passed: 22/100):\n",
      "Proper answer: [-99, -68, -57, -57, -41, -40, -12, -5, 1, 13, 20, 22, 25, 30, 36, 56, 57, 64, 81, 92, 94]\n",
      "After sorting: [-99, -68, -57, -57, -41, -40, -12, -5, 1, 13, 20, 22, 25, 30, 36, 56, 57, 64, 81, 92, 94]\n",
      "\n",
      "#23 Loop (passed: 23/100):\n",
      "Proper answer: [-98, -97, -86, -70, -69, -57, -54, -49, -27, -17, -11, -6, 2, 10, 27, 36, 39, 41, 42, 42, 68, 79, 86, 100]\n",
      "After sorting: [-98, -97, -86, -70, -69, -57, -54, -49, -27, -17, -11, -6, 2, 10, 27, 36, 39, 41, 42, 42, 68, 79, 86, 100]\n",
      "\n",
      "#24 Loop (passed: 24/100):\n",
      "Proper answer: [-87, -57, -53, -41, -41, -34, -24, -22, -14, -12, 6, 26, 34, 37, 37, 52, 64, 72, 77, 87, 89, 93, 96]\n",
      "After sorting: [-87, -57, -53, -41, -41, -34, -24, -22, -14, -12, 6, 26, 34, 37, 37, 52, 64, 72, 77, 87, 89, 93, 96]\n",
      "\n",
      "#25 Loop (passed: 25/100):\n",
      "Proper answer: [-94, -92, -88, -60, -51, -21, -8, -4, 8, 18, 25, 41, 43, 45, 64, 77, 96, 97]\n",
      "After sorting: [-94, -92, -88, -60, -51, -21, -8, -4, 8, 18, 25, 41, 43, 45, 64, 77, 96, 97]\n",
      "\n",
      "#26 Loop (passed: 26/100):\n",
      "Proper answer: [-95, -89, -89, -57, -43, -43, -35, -16, -9, 0, 0, 3, 10, 19, 23, 24, 27, 35, 47, 51, 58, 62, 81, 95]\n",
      "After sorting: [-95, -89, -89, -57, -43, -43, -35, -16, -9, 0, 0, 3, 10, 19, 23, 24, 27, 35, 47, 51, 58, 62, 81, 95]\n",
      "\n",
      "#27 Loop (passed: 27/100):\n",
      "Proper answer: [-80, -78, -74, -72, -43, -43, -1, 3, 4, 9, 14, 18, 27, 36, 44, 52, 52, 57, 58, 78, 79, 84]\n",
      "After sorting: [-80, -78, -74, -72, -43, -43, -1, 3, 4, 9, 14, 18, 27, 36, 44, 52, 52, 57, 58, 78, 79, 84]\n",
      "\n",
      "#28 Loop (passed: 28/100):\n",
      "Proper answer: [-100, -99, -90, -78, -66, -64, -61, -60, -48, -31, -26, -22, -22, -19, -12, 0, 7, 11, 14, 43, 43, 59, 75, 77, 83, 96, 97]\n",
      "After sorting: [-100, -99, -90, -78, -66, -64, -61, -60, -48, -31, -26, -22, -22, -19, -12, 0, 7, 11, 14, 43, 43, 59, 75, 77, 83, 96, 97]\n",
      "\n",
      "#29 Loop (passed: 29/100):\n",
      "Proper answer: [-98, -96, -83, -80, -72, -59, -59, -49, -48, -45, -43, -20, -17, -13, -8, -3, 3, 14, 18, 23, 29, 30, 40, 42, 43, 46, 69, 84, 90, 94]\n",
      "After sorting: [-98, -96, -83, -80, -72, -59, -59, -49, -48, -45, -43, -20, -17, -13, -8, -3, 3, 14, 18, 23, 29, 30, 40, 42, 43, 46, 69, 84, 90, 94]\n",
      "\n",
      "#30 Loop (passed: 30/100):\n",
      "Proper answer: [-94, -20, -12, 2, 48, 57, 60, 71, 74, 98]\n",
      "After sorting: [-94, -20, -12, 2, 48, 57, 60, 71, 74, 98]\n",
      "\n",
      "#31 Loop (passed: 31/100):\n",
      "Proper answer: [-79, -60, -35, -31, -10, 27, 29, 44, 60, 72, 81, 89, 91]\n",
      "After sorting: [-79, -60, -35, -31, -10, 27, 29, 44, 60, 72, 81, 89, 91]\n",
      "\n",
      "#32 Loop (passed: 32/100):\n",
      "Proper answer: [-94, -85, -84, -80, -57, -49, -35, -33, -24, -18, -17, -6, -6, -4, 45, 51, 55, 62, 71, 87, 100, 100]\n",
      "After sorting: [-94, -85, -84, -80, -57, -49, -35, -33, -24, -18, -17, -6, -6, -4, 45, 51, 55, 62, 71, 87, 100, 100]\n",
      "\n",
      "#33 Loop (passed: 33/100):\n",
      "Proper answer: [-74, -73, -72, -71, -71, -38, -34, -18, -15, -12, -4, 14, 19, 23, 72, 76, 78, 83, 98]\n",
      "After sorting: [-74, -73, -72, -71, -71, -38, -34, -18, -15, -12, -4, 14, 19, 23, 72, 76, 78, 83, 98]\n",
      "\n",
      "#34 Loop (passed: 34/100):\n",
      "Proper answer: [-93, -79, -73, -70, -67, -64, -36, -26, -25, -18, -6, 0, 3, 11, 12, 25, 45, 56, 64, 65, 82, 93]\n",
      "After sorting: [-93, -79, -73, -70, -67, -64, -36, -26, -25, -18, -6, 0, 3, 11, 12, 25, 45, 56, 64, 65, 82, 93]\n",
      "\n",
      "#35 Loop (passed: 35/100):\n",
      "Proper answer: [-96, -95, -86, -78, -57, -51, -47, -30, -28, -28, -20, -3, -1, 2, 5, 22, 24, 26, 28, 34, 34, 38, 50, 61, 67, 69, 70, 79, 89]\n",
      "After sorting: [-96, -95, -86, -78, -57, -51, -47, -30, -28, -28, -20, -3, -1, 2, 5, 22, 24, 26, 28, 34, 34, 38, 50, 61, 67, 69, 70, 79, 89]\n",
      "\n",
      "#36 Loop (passed: 36/100):\n",
      "Proper answer: [-88, -88, -73, -68, -68, -45, -42, -40, -39, -36, -22, -22, -17, -15, 13, 15, 16, 16, 22, 26, 30, 42, 54, 55, 60, 75, 79, 83, 84]\n",
      "After sorting: [-88, -88, -73, -68, -68, -45, -42, -40, -39, -36, -22, -22, -17, -15, 13, 15, 16, 16, 22, 26, 30, 42, 54, 55, 60, 75, 79, 83, 84]\n",
      "\n",
      "#37 Loop (passed: 37/100):\n",
      "Proper answer: [-54, -2, 3, 4, 12, 66, 98]\n",
      "After sorting: [-54, -2, 3, 4, 12, 66, 98]\n",
      "\n",
      "#38 Loop (passed: 38/100):\n",
      "Proper answer: [-99, -93, -68, -67, -50, -18, -18, -9, 31, 41, 44, 65, 72, 76, 93, 94, 97, 98]\n",
      "After sorting: [-99, -93, -68, -67, -50, -18, -18, -9, 31, 41, 44, 65, 72, 76, 93, 94, 97, 98]\n",
      "\n",
      "#39 Loop (passed: 39/100):\n",
      "Proper answer: [-44, -27, -21, 9, 20, 59, 71, 77]\n",
      "After sorting: [-44, -27, -21, 9, 20, 59, 71, 77]\n",
      "\n",
      "#40 Loop (passed: 40/100):\n",
      "Proper answer: [-97, -93, -71, -71, -52, -47, -36, -28, -17, -4, 3, 8, 32, 40, 40, 42, 45, 45, 58, 61, 64, 65, 70, 79, 93, 93]\n",
      "After sorting: [-97, -93, -71, -71, -52, -47, -36, -28, -17, -4, 3, 8, 32, 40, 40, 42, 45, 45, 58, 61, 64, 65, 70, 79, 93, 93]\n",
      "\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#41 Loop (passed: 41/100):\n",
      "Proper answer: [-96, -82, -78, -72, -56, -50, -49, -24, 5, 36, 42, 47, 58, 68, 73, 89, 89]\n",
      "After sorting: [-96, -82, -78, -72, -56, -50, -49, -24, 5, 36, 42, 47, 58, 68, 73, 89, 89]\n",
      "\n",
      "#42 Loop (passed: 42/100):\n",
      "Proper answer: [-89, -68, -46, -37, -23, -19, -5, 5, 8, 12, 13, 32, 35, 38, 45, 48, 55, 58, 85, 88, 99, 100, 100]\n",
      "After sorting: [-89, -68, -46, -37, -23, -19, -5, 5, 8, 12, 13, 32, 35, 38, 45, 48, 55, 58, 85, 88, 99, 100, 100]\n",
      "\n",
      "#43 Loop (passed: 43/100):\n",
      "Proper answer: [-94, -91, -85, -75, -47, -7, -3, 10, 13, 15, 22, 22, 23, 24, 35, 37, 41, 66, 78, 91, 97]\n",
      "After sorting: [-94, -91, -85, -75, -47, -7, -3, 10, 13, 15, 22, 22, 23, 24, 35, 37, 41, 66, 78, 91, 97]\n",
      "\n",
      "#44 Loop (passed: 44/100):\n",
      "Proper answer: [-94, -85, -66, -54, -48, -24, -3, 30, 42, 66, 75]\n",
      "After sorting: [-94, -85, -66, -54, -48, -24, -3, 30, 42, 66, 75]\n",
      "\n",
      "#45 Loop (passed: 45/100):\n",
      "Proper answer: [-99, -99, -78, -74, -62, -44, -38, -24, 4, 5, 39, 44, 71, 92]\n",
      "After sorting: [-99, -99, -78, -74, -62, -44, -38, -24, 4, 5, 39, 44, 71, 92]\n",
      "\n",
      "#46 Loop (passed: 46/100):\n",
      "Proper answer: [-98, -93, -63, -41, -12, 2, 9, 13, 45, 91]\n",
      "After sorting: [-98, -93, -63, -41, -12, 2, 9, 13, 45, 91]\n",
      "\n",
      "#47 Loop (passed: 47/100):\n",
      "Proper answer: [-100, -96, -91, -90, -88, -86, -76, -64, -59, -40, 7, 64, 69, 86, 90, 95, 100]\n",
      "After sorting: [-100, -96, -91, -90, -88, -86, -76, -64, -59, -40, 7, 64, 69, 86, 90, 95, 100]\n",
      "\n",
      "#48 Loop (passed: 48/100):\n",
      "Proper answer: [-97, -97, -94, -91, -74, -66, -63, -41, -34, -20, 27, 29, 34, 36, 36, 38, 45, 57, 74, 83, 85, 86, 88, 92, 93]\n",
      "After sorting: [-97, -97, -94, -91, -74, -66, -63, -41, -34, -20, 27, 29, 34, 36, 36, 38, 45, 57, 74, 83, 85, 86, 88, 92, 93]\n",
      "\n",
      "#49 Loop (passed: 49/100):\n",
      "Proper answer: [-91, -81, -78, -58, -6, 51, 70, 88, 94]\n",
      "After sorting: [-91, -81, -78, -58, -6, 51, 70, 88, 94]\n",
      "\n",
      "#50 Loop (passed: 50/100):\n",
      "Proper answer: [-92, -75, -70, -60, -38, -29, -23, -14, -7, -6, -2, 5, 7, 9, 27, 30, 52, 96]\n",
      "After sorting: [-92, -75, -70, -60, -38, -29, -23, -14, -7, -6, -2, 5, 7, 9, 27, 30, 52, 96]\n",
      "\n",
      "#51 Loop (passed: 51/100):\n",
      "Proper answer: [-88, -68, -41, -37, 3, 14, 26, 26, 38, 47, 50, 55, 81, 91]\n",
      "After sorting: [-88, -68, -41, -37, 3, 14, 26, 26, 38, 47, 50, 55, 81, 91]\n",
      "\n",
      "#52 Loop (passed: 52/100):\n",
      "Proper answer: [-87, -75, -66, -62, -58, -48, -43, -40, -39, -37, -36, -28, -17, -12, -2, 11, 25, 29, 35, 38, 40, 44, 62, 74, 75, 75, 80, 88, 96]\n",
      "After sorting: [-87, -75, -66, -62, -58, -48, -43, -40, -39, -37, -36, -28, -17, -12, -2, 11, 25, 29, 35, 38, 40, 44, 62, 74, 75, 75, 80, 88, 96]\n",
      "\n",
      "#53 Loop (passed: 53/100):\n",
      "Proper answer: [-91, -90, -78, -71, -60, -26, -25, -19, -13, 11, 19, 27, 31, 71, 78, 95, 100]\n",
      "After sorting: [-91, -90, -78, -71, -60, -26, -25, -19, -13, 11, 19, 27, 31, 71, 78, 95, 100]\n",
      "\n",
      "#54 Loop (passed: 54/100):\n",
      "Proper answer: [-92, -77, -77, -64, -49, -44, -22, -6, -4, 21, 31, 46, 48, 54]\n",
      "After sorting: [-92, -77, -77, -64, -49, -44, -22, -6, -4, 21, 31, 46, 48, 54]\n",
      "\n",
      "#55 Loop (passed: 55/100):\n",
      "Proper answer: [-97, -89, -88, -66, -53, -52, -52, -24, -18, -17, 8, 9, 10, 11, 11, 15, 19, 29, 36, 39, 48, 56, 71, 85, 93, 95]\n",
      "After sorting: [-97, -89, -88, -66, -53, -52, -52, -24, -18, -17, 8, 9, 10, 11, 11, 15, 19, 29, 36, 39, 48, 56, 71, 85, 93, 95]\n",
      "\n",
      "#56 Loop (passed: 56/100):\n",
      "Proper answer: [-92, -90, -81, -56, -6, 30, 32]\n",
      "After sorting: [-92, -90, -81, -56, -6, 30, 32]\n",
      "\n",
      "#57 Loop (passed: 57/100):\n",
      "Proper answer: [-81, -66, -57, -36, -33, -28, -27, -27, -17, -13, 43, 60, 60, 67, 68, 70, 71, 78, 99]\n",
      "After sorting: [-81, -66, -57, -36, -33, -28, -27, -27, -17, -13, 43, 60, 60, 67, 68, 70, 71, 78, 99]\n",
      "\n",
      "#58 Loop (passed: 58/100):\n",
      "Proper answer: [-85, -84, -75, -70, -67, -62, -56, -50, -47, -43, -42, -39, -29, -20, -17, -14, 2, 7, 25, 25, 55, 63, 65, 73, 80]\n",
      "After sorting: [-85, -84, -75, -70, -67, -62, -56, -50, -47, -43, -42, -39, -29, -20, -17, -14, 2, 7, 25, 25, 55, 63, 65, 73, 80]\n",
      "\n",
      "#59 Loop (passed: 59/100):\n",
      "Proper answer: [-56, -55, 51, 68, 72]\n",
      "After sorting: [-56, -55, 51, 68, 72]\n",
      "\n",
      "#60 Loop (passed: 60/100):\n",
      "Proper answer: [-88, -73, 54, 64, 94, 97]\n",
      "After sorting: [-88, -73, 54, 64, 94, 97]\n",
      "\n",
      "#61 Loop (passed: 61/100):\n",
      "Proper answer: [-82, -76, -64, -46, -38, -33, -32, -17, 2, 18, 35, 44, 44, 45, 46, 66]\n",
      "After sorting: [-82, -76, -64, -46, -38, -33, -32, -17, 2, 18, 35, 44, 44, 45, 46, 66]\n",
      "\n",
      "#62 Loop (passed: 62/100):\n",
      "Proper answer: [-41, -28, -19, -9, -6]\n",
      "After sorting: [-41, -28, -19, -9, -6]\n",
      "\n",
      "#63 Loop (passed: 63/100):\n",
      "Proper answer: [-100, -96, -79, -77, -72, -68, -32, -24, -15, -11, -8, -7, -3, -3, 7, 60, 85, 86, 95, 95]\n",
      "After sorting: [-100, -96, -79, -77, -72, -68, -32, -24, -15, -11, -8, -7, -3, -3, 7, 60, 85, 86, 95, 95]\n",
      "\n",
      "#64 Loop (passed: 64/100):\n",
      "Proper answer: [-83, -82, -57, -47, -33, 2, 3, 3, 3, 9, 13, 29, 38, 53, 53, 59, 73, 90, 99]\n",
      "After sorting: [-83, -82, -57, -47, -33, 2, 3, 3, 3, 9, 13, 29, 38, 53, 53, 59, 73, 90, 99]\n",
      "\n",
      "#65 Loop (passed: 65/100):\n",
      "Proper answer: [-95, -68, -44, -37, -12, -7, -4, 27, 48, 61, 91]\n",
      "After sorting: [-95, -68, -44, -37, -12, -7, -4, 27, 48, 61, 91]\n",
      "\n",
      "#66 Loop (passed: 66/100):\n",
      "Proper answer: [-94, -93, -81, -80, -76, -72, -61, -47, -39, -31, -28, -16, -8, -8, -5, 15, 15, 24, 40, 50, 51, 62, 63, 71, 71, 74]\n",
      "After sorting: [-94, -93, -81, -80, -76, -72, -61, -47, -39, -31, -28, -16, -8, -8, -5, 15, 15, 24, 40, 50, 51, 62, 63, 71, 71, 74]\n",
      "\n",
      "#67 Loop (passed: 67/100):\n",
      "Proper answer: [-94, -84, -82, -80, -75, -75, -69, -65, -34, -34, -30, -8, -7, 6, 13, 15, 25, 25, 30, 34, 44, 46, 49, 59, 68, 71, 76, 83, 99]\n",
      "After sorting: [-94, -84, -82, -80, -75, -75, -69, -65, -34, -34, -30, -8, -7, 6, 13, 15, 25, 25, 30, 34, 44, 46, 49, 59, 68, 71, 76, 83, 99]\n",
      "\n",
      "#68 Loop (passed: 68/100):\n",
      "Proper answer: [-94, -79, -25, 15, 51]\n",
      "After sorting: [-94, -79, -25, 15, 51]\n",
      "\n",
      "#69 Loop (passed: 69/100):\n",
      "Proper answer: [-100, -89, -69, -65, -53, -51, -49, -27, -1, 0, 5, 16, 22, 26, 28, 28, 32, 35, 48, 55, 66, 69, 79, 83, 89, 90, 93, 96]\n",
      "After sorting: [-100, -89, -69, -65, -53, -51, -49, -27, -1, 0, 5, 16, 22, 26, 28, 28, 32, 35, 48, 55, 66, 69, 79, 83, 89, 90, 93, 96]\n",
      "\n",
      "#70 Loop (passed: 70/100):\n",
      "Proper answer: [-86, -81, -80, -65, -59, -57, -55, -33, -29, -18, -13, 3, 10, 17, 25, 38, 43, 64, 68, 74, 74]\n",
      "After sorting: [-86, -81, -80, -65, -59, -57, -55, -33, -29, -18, -13, 3, 10, 17, 25, 38, 43, 64, 68, 74, 74]\n",
      "\n",
      "#71 Loop (passed: 71/100):\n",
      "Proper answer: [-96, -25, -15, 5, 63, 88]\n",
      "After sorting: [-96, -25, -15, 5, 63, 88]\n",
      "\n",
      "#72 Loop (passed: 72/100):\n",
      "Proper answer: [-99, -97, -96, -63, -58, -53, -48, -48, -48, -47, -32, -31, -29, -12, 2, 16, 31, 43, 47, 52, 62, 63, 65, 83, 90, 97]\n",
      "After sorting: [-99, -97, -96, -63, -58, -53, -48, -48, -48, -47, -32, -31, -29, -12, 2, 16, 31, 43, 47, 52, 62, 63, 65, 83, 90, 97]\n",
      "\n",
      "#73 Loop (passed: 73/100):\n",
      "Proper answer: [-91, -91, -88, -85, -83, -69, -53, -47, -45, -39, -34, -8, 7, 18, 25, 26, 29, 38, 41, 41, 57, 64, 65, 71, 100]\n",
      "After sorting: [-91, -91, -88, -85, -83, -69, -53, -47, -45, -39, -34, -8, 7, 18, 25, 26, 29, 38, 41, 41, 57, 64, 65, 71, 100]\n",
      "\n",
      "#74 Loop (passed: 74/100):\n",
      "Proper answer: [-83, -77, -68, -57, 2, 14, 28, 39, 43, 51, 68]\n",
      "After sorting: [-83, -77, -68, -57, 2, 14, 28, 39, 43, 51, 68]\n",
      "\n",
      "#75 Loop (passed: 75/100):\n",
      "Proper answer: [-100, -91, -84, -83, -82, -67, -54, -25, -12, -12, -10, 2, 45, 73, 76, 76, 78]\n",
      "After sorting: [-100, -91, -84, -83, -82, -67, -54, -25, -12, -12, -10, 2, 45, 73, 76, 76, 78]\n",
      "\n",
      "#76 Loop (passed: 76/100):\n",
      "Proper answer: [-90, -65, -56, -52, -51, -37, -37, -35, 33, 44, 46, 50, 54, 55, 73, 98]\n",
      "After sorting: [-90, -65, -56, -52, -51, -37, -37, -35, 33, 44, 46, 50, 54, 55, 73, 98]\n",
      "\n",
      "#77 Loop (passed: 77/100):\n",
      "Proper answer: [-77, -76, -65, -61, -54, -34, 40, 44, 71]\n",
      "After sorting: [-77, -76, -65, -61, -54, -34, 40, 44, 71]\n",
      "\n",
      "#78 Loop (passed: 78/100):\n",
      "Proper answer: [-87, -72, -58, -32, -3, 12, 13, 19, 46, 53, 56, 71, 80]\n",
      "After sorting: [-87, -72, -58, -32, -3, 12, 13, 19, 46, 53, 56, 71, 80]\n",
      "\n",
      "#79 Loop (passed: 79/100):\n",
      "Proper answer: [-99, -87, -48, -46, 15, 17, 26, 30, 33, 33, 48, 61, 73, 78, 86]\n",
      "After sorting: [-99, -87, -48, -46, 15, 17, 26, 30, 33, 33, 48, 61, 73, 78, 86]\n",
      "\n",
      "#80 Loop (passed: 80/100):\n",
      "Proper answer: [-80, -80, -78, -77, -75, -62, -61, -60, -26, -24, -21, -3, -2, 4, 43, 57, 84, 86, 92, 96, 98, 100, 100]\n",
      "After sorting: [-80, -80, -78, -77, -75, -62, -61, -60, -26, -24, -21, -3, -2, 4, 43, 57, 84, 86, 92, 96, 98, 100, 100]\n",
      "\n",
      "#81 Loop (passed: 81/100):\n",
      "Proper answer: [-95, -59, -58, -6, -6, 5, 48, 55, 72, 90]\n",
      "After sorting: [-95, -59, -58, -6, -6, 5, 48, 55, 72, 90]\n",
      "\n",
      "#82 Loop (passed: 82/100):\n",
      "Proper answer: [-98, -93, -64, -32, -8, 24, 32, 43, 46, 60, 62, 72, 73, 86, 97]\n",
      "After sorting: [-98, -93, -64, -32, -8, 24, 32, 43, 46, 60, 62, 72, 73, 86, 97]\n",
      "\n",
      "#83 Loop (passed: 83/100):\n",
      "Proper answer: [-99, -98, -77, -73, -70, -64, -59, -36, -28, -16, -12, -8, 21, 31, 45, 62, 66, 96, 98]\n",
      "After sorting: [-99, -98, -77, -73, -70, -64, -59, -36, -28, -16, -12, -8, 21, 31, 45, 62, 66, 96, 98]\n",
      "\n",
      "#84 Loop (passed: 84/100):\n",
      "Proper answer: [-94, -28, 10, 55, 83]\n",
      "After sorting: [-94, -28, 10, 55, 83]\n",
      "\n",
      "#85 Loop (passed: 85/100):\n",
      "Proper answer: [-100, -22, -9, -8, -6, 3, 62, 83, 85]\n",
      "After sorting: [-100, -22, -9, -8, -6, 3, 62, 83, 85]\n",
      "\n",
      "#86 Loop (passed: 86/100):\n",
      "Proper answer: [-100, -100, -95, -94, -87, -80, -62, -56, -55, -51, -35, -28, -21, -14, -12, -11, 4, 12, 26, 56]\n",
      "After sorting: [-100, -100, -95, -94, -87, -80, -62, -56, -55, -51, -35, -28, -21, -14, -12, -11, 4, 12, 26, 56]\n",
      "\n",
      "#87 Loop (passed: 87/100):\n",
      "Proper answer: [-61, -43, -7, 6, 10, 24, 66, 73, 74, 87]\n",
      "After sorting: [-61, -43, -7, 6, 10, 24, 66, 73, 74, 87]\n",
      "\n",
      "#88 Loop (passed: 88/100):\n",
      "Proper answer: [-99, -95, -81, -67, -60, -48, -39, -36, -18, -13, -9, 1, 4, 9, 55, 56, 75, 92]\n",
      "After sorting: [-99, -95, -81, -67, -60, -48, -39, -36, -18, -13, -9, 1, 4, 9, 55, 56, 75, 92]\n",
      "\n",
      "#89 Loop (passed: 89/100):\n",
      "Proper answer: [-98, -11, -6, 13, 48]\n",
      "After sorting: [-98, -11, -6, 13, 48]\n",
      "\n",
      "#90 Loop (passed: 90/100):\n",
      "Proper answer: [-98, -93, -92, -77, -73, -71, -54, -51, -49, -33, -32, -31, -30, -25, -16, -14, 11, 15, 15, 16, 33, 38, 42, 55, 56, 57, 79, 87, 92]\n",
      "After sorting: [-98, -93, -92, -77, -73, -71, -54, -51, -49, -33, -32, -31, -30, -25, -16, -14, 11, 15, 15, 16, 33, 38, 42, 55, 56, 57, 79, 87, 92]\n",
      "\n",
      "#91 Loop (passed: 91/100):\n",
      "Proper answer: [-87, -69, -67, -60, -30, -30, -28, -10, -6, 2, 13, 35, 50, 51, 51, 57]\n",
      "After sorting: [-87, -69, -67, -60, -30, -30, -28, -10, -6, 2, 13, 35, 50, 51, 51, 57]\n",
      "\n",
      "#92 Loop (passed: 92/100):\n",
      "Proper answer: [-97, -94, -91, -86, -72, -70, -61, -53, -46, -43, -32, -20, -19, -19, -4, -1, -1, 3, 12, 22, 29, 34, 42, 57, 81, 83, 90, 96, 99]\n",
      "After sorting: [-97, -94, -91, -86, -72, -70, -61, -53, -46, -43, -32, -20, -19, -19, -4, -1, -1, 3, 12, 22, 29, 34, 42, 57, 81, 83, 90, 96, 99]\n",
      "\n",
      "#93 Loop (passed: 93/100):\n",
      "Proper answer: [-90, -88, -83, -62, -46, -45, -30, 18, 36, 43, 53, 53, 61, 89]\n",
      "After sorting: [-90, -88, -83, -62, -46, -45, -30, 18, 36, 43, 53, 53, 61, 89]\n",
      "\n",
      "#94 Loop (passed: 94/100):\n",
      "Proper answer: [-98, -87, -82, -69, -65, -61, -56, -25, -5, 12, 20, 29, 40, 43, 44, 52, 56, 57, 57, 87]\n",
      "After sorting: [-98, -87, -82, -69, -65, -61, -56, -25, -5, 12, 20, 29, 40, 43, 44, 52, 56, 57, 57, 87]\n",
      "\n",
      "#95 Loop (passed: 95/100):\n",
      "Proper answer: [-95, -95, -90, -88, -84, -80, -78, -75, -66, -66, -50, -49, -43, -21, -18, -15, -15, 1, 11, 19, 20, 21, 30, 63, 71, 81, 84]\n",
      "After sorting: [-95, -95, -90, -88, -84, -80, -78, -75, -66, -66, -50, -49, -43, -21, -18, -15, -15, 1, 11, 19, 20, 21, 30, 63, 71, 81, 84]\n",
      "\n",
      "#96 Loop (passed: 96/100):\n",
      "Proper answer: [-85, -84, -77, -54, -46, -46, -36, -31, 0, 7, 19, 44, 52, 67, 93]\n",
      "After sorting: [-85, -84, -77, -54, -46, -46, -36, -31, 0, 7, 19, 44, 52, 67, 93]\n",
      "\n",
      "#97 Loop (passed: 97/100):\n",
      "Proper answer: [-86, -51, -50, -49, -47, -31, -31, -20, -20, -18, -17, -16, 16, 17, 17, 21, 34, 34, 36, 77, 86, 87, 89, 91, 94]\n",
      "After sorting: [-86, -51, -50, -49, -47, -31, -31, -20, -20, -18, -17, -16, 16, 17, 17, 21, 34, 34, 36, 77, 86, 87, 89, 91, 94]\n",
      "\n",
      "#98 Loop (passed: 98/100):\n",
      "Proper answer: [-99, -93, -90, -82, -81, -71, -71, -63, -48, -46, -43, -26, -12, 6, 24, 28, 35, 39, 40, 47, 49, 55, 55, 61, 65, 79, 85]\n",
      "After sorting: [-99, -93, -90, -82, -81, -71, -71, -63, -48, -46, -43, -26, -12, 6, 24, 28, 35, 39, 40, 47, 49, 55, 55, 61, 65, 79, 85]\n",
      "\n",
      "#99 Loop (passed: 99/100):\n",
      "Proper answer: [-94, -64, -48, -30, 11]\n",
      "After sorting: [-94, -64, -48, -30, 11]\n",
      "\n",
      "#100 Loop (passed: 100/100):\n",
      "Proper answer: [-98, -93, -76, -71, -65, -25, -6, 16, 21, 36, 50, 84, 95]\n",
      "After sorting: [-98, -93, -76, -71, -65, -25, -6, 16, 21, 36, 50, 84, 95]\n",
      "\n",
      "Total passed tests: 100/100\n",
      "A sorting algorithm is implemented correctly\n"
     ]
    }
   ],
   "source": [
    "test_sort(bubble_sort, samples=100)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}